1. 算法简介

快速排序（Quick Sort）是由英国计算机科学家霍尔（C.A.R. Hoare）在1960年提出的一种高效的排序算法。它采用了分治法（Divide and Conquer）策略，通常具有很好的性能。在平均情况下，快速排序的时间复杂度为 O(n log n)，但在最坏情况下可能退化为 O(n^2)，不过可以通过优化策略（如随机化或三数取中法）来避免这种情况。

1.1 算法步骤

1. 选择基准元素：从待排序的数组中选择一个元素作为基准（pivot）。
2. 划分操作：将数组重新排列，使得比基准小的元素排在左边，比基准大的元素排在右边。此时，基准元素已处于排序后的正确位置。
3. 递归操作：递归地对基准左边和右边的子数组进行快速排序。

1.2 优缺点

优点：

• 平均情况下时间复杂度为 O(n log n)，性能较好。
• 空间复杂度较低，只需 O(log n) 的栈空间（递归深度）。

缺点：

• 最坏情况下时间复杂度为 O(n^2)，但可以通过随机化选择基准来优化。
• 不稳定排序，排序过程中可能会改变相同元素的相对顺序。

---

2. 使用 C 实现快速排序

首先，我们来看看如何用 C 语言实现快速排序。C 语言作为一种底层编程语言，能够提供很好的性能和灵活性。

2.1 C 代码实现

#include <stdio.h>

// 函数：交换数组中的两个元素
void swap(int *a, int *b) {
   
    
      
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 函数：划分操作，选择基准元素并划分数组
int partition(int arr[], int low, int high) {
   
    
      
    // 选择最后一个元素作为基准
    int pivot = arr[high];
    int i = low - 1; // i是小于基准元素的子数组的最后一个元素索引
    
    for (int j = low; j < high; j++) {
   
    
      
        // 如果当前元素小于等于基准元素
        if (arr[j] <= pivot) {
   
    
      
            i++;
            // 交换元素
            swap(&arr[i], &arr[j]);
        }
    }
    // 将基准元素放置到正确的位置