快速排序

快速排序（Quick Sort）是由 Tony Hoare 在 1960 年提出的一种基于分治法的排序算法，是目前内部排序中综合性能最好的算法之一。

核心思想：从待排序序列中选取一个元素作为枢轴（pivot），通过一趟排序将序列划分为左右两个子序列——左子序列中所有元素 $\leq pivot$，右子序列中所有元素 $> pivot$。然后对左右子序列递归执行相同操作，直到整个序列有序。

快速排序的排序过程类似于构建二叉排序树（BST）：每次选取一个根节点，将比它小的放左边、比它大的放右边。因此快速排序的递归树结构与 BST 高度相关。

关键特性

• 快速排序是交换排序的一种，但它不是简单地两两交换，而是通过一趟划分确定一个元素的最终位置
• 每趟排序会确定一个（或多个）元素的最终位置
• 快速排序不产生有序子序列（区别于冒泡排序和插入排序）
• 是内部排序中平均性能最好的算法
• 原地排序（in-place）：不需要额外数组空间，仅需递归栈空间

一趟划分（Partition）过程

1. 选取序列中某个元素作为枢轴 pivot（通常选第一个元素 L[low]）
2. 初始化两个指针：low 指向序列开头，high 指向序列末尾
3. 先从右往左扫描：当 high 指向的元素 $\geq pivot$ 时，high--；否则将 L[high] 移到 low 位置
4. 再从左往右扫描：当 low 指向的元素 $\leq pivot$ 时，low++；否则将 L[low] 移到 high 位置
5. 重复步骤 3-4，直到 low == high
6. 将 pivot 放入 low == high 指向的位置，此时 pivot 已到达最终位置

递归过程

7. 对 pivot 左边的子序列 [low, pivot-1] 递归执行快速排序
8. 对 pivot 右边的子序列 [pivot+1, high] 递归执行快速排序
9. 递归终止条件：low >= high（子序列长度 $\leq 1$）

代码实现（双边循环法）

int Partition(int A[], int low, int high) {
    int pivot = A[low];  // 选取第一个元素作为枢轴
    while (low < high) {
        // 从右往左找比 pivot 小的元素
        while (low < high && A[high] >= pivot)
            high--;
        A[low] = A[high];
        // 从左往右找比 pivot 大的元素
        while (low < high && A[low] <= pivot)
            low++;
        A[high] = A[low];
    }
    A[low] = pivot;  // pivot 放到最终位置
    return low;
}

void QuickSort(int A[], int low, int high) {
    if (low < high) {
        int pivotpos = Partition(A, low, high);
        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
    }
}

优化版本：三数取中法选枢轴

int MedianOfThree(int A[], int low, int high) {
    int mid = low + (high - low) / 2;
    if (A[low] > A[mid])  swap(A[low], A[mid]);
    if (A[low] > A[high]) swap(A[low], A[high]);
    if (A[mid] > A[high]) swap(A[mid], A[high]);
    swap(A[mid], A[high-1]);  // 中位数放到 high-1 位置
    return A[high-1];
}

更多优化见 quick-sort-optimization。

对序列 49, 38, 65, 97, 76, 13, 27, 49* 进行快速排序（首元素作枢轴）：

第一趟划分（$pivot = 49$）：

初始:  49  38  65  97  76  13  27  49*
       ↑low                            ↑high

从右扫描: 27 < 49, high 停在 27
       27  38  65  97  76  13  [27] 49*
       ↑low                      ↑high

从左扫描: 65 > 49, low 停在 65
       27  38  [65]  97  76  13  65  49*
           ↑low              ↑high

从右扫描: 13 < 49, high 停在 13
       27  38  13  97  76  [13]  65  49*
           ↑low        ↑high

从左扫描: 97 > 49, low 停在 97
       27  38  13  [97]  76  97  65  49*
               ↑low  ↑high

low == high, 放入 pivot:
       27  38  13  [49]  76  97  65  49*
               ↑pivot

结果：$pivot=49$ 到达最终位置，左子表 {27, 38, 13}，右子表 {76, 97, 65, 49*}。

第二趟：对左子表 {27, 38, 13}（$pivot=27$）和右子表 {76, 97, 65, 49*}（$pivot=76$）分别划分。

继续递归直到所有子序列长度 $\leq 1$。最终排序结果：13, 27, 38, 49, 49*, 65, 76, 97。