考研笔记

板子：快速排序（教材版 Partition）

取一个枢轴，一趟划分把比它小的放左边、比它大的放右边，枢轴就落在了最终位置。然后对左右两段分别递归。 **这里严格按教材口径写：枢轴取区间的最后一个元素，用填坑法，先从前往后走。**手算「第一趟划分后的序列」必须按这个口径。

代码

int Partition(int A[], int low, int high) {  // 划分 A[low..high]，返回枢轴的最终位置
    int i = low, j = high;
    int pivot = A[j];                        // 枢轴取最后一个元素，A[j] 变成一个「坑」
    while (i < j) {
        while (i < j && A[i] <= pivot) i++;  // 从前往后，找比枢轴大的元素
        if (i < j) A[j] = A[i];              // 把它填进右边的坑，A[i] 变成新的坑
        while (i < j && A[j] >= pivot) j--;  // 从后往前，找比枢轴小的元素
        if (i < j) A[i] = A[j];              // 把它填进左边的坑，A[j] 变成新的坑
    }
    A[i] = pivot;                            // i == j：最后剩下的坑就是枢轴的最终位置
    return i;
}
 
void QuickSort(int A[], int low, int high) {
    if (low >= high) return;                 // 区间里不到 2 个元素，不用排
    int p = Partition(A, low, high);         // 枢轴已经放到 A[p]
    QuickSort(A, low, p - 1);                // 左半段，不包括 p
    QuickSort(A, p + 1, high);               // 右半段，不包括 p
}
// 调用：QuickSort(A, 0, n - 1);

复杂度：平均时间 ，最坏 （每次划分都极不平衡，比如表已经有序）。空间是递归栈，平均 ，最坏 。不稳定。

一趟划分的手算过程

3 8 2 7 1 5，枢轴取最后一个 5：

步动作数组（_ 表示坑）
0取走枢轴 53 8 2 7 1 _
1i 往右走，停在 8（比 5 大），填进右坑3 _ 2 7 1 8
2j 往左走，停在 1（比 5 小），填进左坑3 1 2 7 _ 8
3i 往右走，停在 7，填进右坑3 1 2 _ 7 8
4j 往左走，碰到 i，停下3 1 2 _ 7 8
5枢轴填进最后的坑3 1 2 5 7 8

关键边界

代码为什么
pivot = A[high]，先动 i枢轴拿走以后，坑在右端。要从左边找一个大的元素来填这个坑，所以先让 i 往右走。如果枢轴取第一个元素，坑在左端，就要反过来先动 j
内层循环也要写 i < j防止 i、j 交错或越界。i == j 说明坑已经找到了最终位置
A[i] <= pivot 和 A[j] >= pivot 都带等号和枢轴相等的元素不移动，留在原来那一侧，这样可以少移动几次
if (i < j) 再填内层循环如果是因为 i == j 停下的，填坑就成了自己赋给自己。教材写上这个判断，逻辑更清楚
最后 A[i] = pivot循环结束时 i == j，这个位置就是最后剩下的坑
递归用 p - 1 和 p + 1枢轴已经在最终位置，不再参与后面的排序

易错点

  • 口径：很多书和算竞写法是枢轴取第一个元素、先从后往前走，一趟划分后的序列会不一样。408 手算题按教材口径，完整对照见 8.3 交换排序。
  • 「每一趟至少有一个元素（枢轴）到达最终位置」是判断「用的是不是快排」的依据。
  • 快排的空间复杂度不是 ，因为有递归栈。

链接

反向链接