OpenDSA 全教程

Chapter 13 Sorting

| 关于   «  10. 实现归并排序   ::   目录   ::   12. 堆排序  »

11. 快速排序

11.1. 引言

虽然归并排序采用了最直观的 Divide and Conquer（Divide and Conquer）形式（将列表分成两半，然后对这两半进行排序），但这并不是我们分解排序问题的唯一方式。我们看到，在使用数组实现时，执行归并排序的 Merge Step（Merge Step）并不容易。因此，也许另一种 Divide and Conquer（Divide and Conquer）策略会更高效？

快速排序 得名恰如其分，因为在正确实现时，它是平均情况下最快的通用内存排序算法。它不需要归并排序所需的额外数组，因此空间效率也很高。快速排序被广泛使用，通常是库排序例程中实现的算法，例如 UNIX qsort 函数。有趣的是，快速排序受到极差的最坏情况性能的限制，因此不适用于某些应用。

在介绍快速排序之前，先考虑一下使用二叉搜索树进行排序的实用性。

快速排序首先选择一个称为 枢轴 的值。（这在概念上类似于二叉搜索树中根节点的值。）假设输入数组包含 \(k\) 条记录，其键值小于枢轴。然后重新排列这些记录，使得 \(k\) 个小于枢轴的值被放置在数组的前 \(k\) 个位置（即最左侧），而大于或等于枢轴的值被放置在最后 \(n-k\) 个位置（即最右侧）。这称为数组的 划分 。放置在给定分区中的值彼此之间不需要（且通常不会）有序。唯一的要求是所有值最终都位于正确的分区中。枢轴值本身被放置在位置 \(k\) 。接着，快速排序继续对枢轴两侧生成的子数组进行排序，其中一个大小为 \(k\) ，另一个大小为 \(n-k-1\) 。这些值如何排序？由于快速排序是一种非常优秀的算法，因此对子数组使用快速排序是合适的。

与本章前面介绍的一些排序算法不同，快速排序可能看起来不太“自然”，因为它并非人们在整理实物时通常会采用的方法。但值得注意的是，针对计算机上海量抽象对象的高效排序算法，与我们整理少量物理对象的经验存在显著差异，这并不令人意外。

以下是快速排序的实现。参数 i 和 j 分别定义待排序子数组的左、右索引。对 quicksort 的初始调用应为 quicksort(array, 0, n-1) 。

void quicksort(int[] A, int i, int j) { // Quicksort
    int pivotindex = findpivot(A, i, j);  // Pick a pivot
    swap(A, pivotindex, j);               // Stick pivot at end
    // k will be the first position in the right subarray
    int k = partition(A, i, j-1, A[j]);
    swap(A, k, j);                        // Put pivot in place
    if ((k-i) > 1) { quicksort(A, i, k-1); }  // Sort left partition
    if ((j-k) > 1) { quicksort(A, k+1, j); }  // Sort right partition
}

void quicksort(T[] A, int i, int j) { // Quicksort
  int pivotindex = findpivot(A, i, j);  // Pick a pivot
  swap(A, pivotindex, j);               // Stick pivot at end
  // k will be the first position in the right subarray
  int k = partition(A, i, j-1, A[j]);
  swap(A, k, j);                        // Put pivot in place
  if ((k-i) > 1) { quicksort(A, i, k-1); }  // Sort left partition
  if ((j-k) > 1) { quicksort(A, k+1, j); }  // Sort right partition
}

void quicksort(Comparable* A[], int i, int j) {
  int pivotindex = findpivot(i, j);
  swap(A, pivotindex, j); // Stick pivot at end
  // k will be the first position in the right subarray
  int k = partition(A, i, j-1,A[j]);
  swap(A, k, j);                       // Put pivot in place
  if ((k-i) > 1) quicksort(A, i, k-1); // Sort left partition
  if ((j-k) > 1) quicksort(A, k+1, j); // Sort right partition
}

函数 partition 会将记录移动到合适的分区，然后返回 k ，即右分区的起始位置。注意，枢轴值最初被放置在数组的末尾（位置 j ）。因此， partition 不得影响数组位置 j 的值。分区完成后，枢轴值被放置到位置 k ，这是它在最终有序数组中的正确位置。通过这样做，我们保证至少有一个值（即枢轴）不会在递归调用 qsort 中被处理。即使选择了一个糟糕的枢轴，导致枢轴一侧的分区完全为空，较大的分区也最多包含 \(n-1\) 个记录。

选择枢轴有多种方法。最简单的方法是使用第一个关键字。然而，如果输入已排序或逆序排序，这将导致糟糕的划分，所有值都位于枢轴的一侧。更好的做法是随机选择一个值，从而降低不良输入顺序影响排序的可能性。不幸的是，使用随机数生成器相对开销较大，而通过选择数组的中间位置，我们几乎可以达到同样的效果。下面是一个简单的 findpivot 函数。

int findpivot(int[] A, int i, int j)
{ return (i+j)/2; }

int findpivot(T[] A, int i, int j) { return (i+j)/2; }

int findpivot(int i, int j)
  { return (i+j)/2; }

11.2. 划分

现在我们转向函数 partition 。如果我们事先知道有多少个键值小于枢轴， partition 就可以简单地将键值小于枢轴的记录复制到数组的低端，而将键值较大的记录复制到高端。由于我们事先不知道有多少个键值小于枢轴，因此我们使用一种巧妙的算法，该算法从子数组的两端向内移动索引，并在必要时交换值，直到两个索引相遇。以下是分区步骤的实现。

int partition(int[] A, int left, int right, int pivot) {
    while (left <= right) { // Move bounds inward until they meet
        while (A[left] < pivot) { left++; }
        while ((right >= left) && (A[right] >= pivot)) { right--; }
        if (right > left) { swap(A, left, right); } // Swap out-of-place values
    }
    return left;            // Return first position in right partition
}

int partition(T[] A, int left, int right, T pivot) {
  while (left <= right) { // Move bounds inward until they meet
    while (A[left].compareTo(pivot) < 0) { left++; }
    while ((right >= left) && (A[right].compareTo(pivot) >= 0)) { right--; }
    if (right > left) { swap(A, left, right); } // Swap out-of-place values
  }
  return left;            // Return first position in right partition
}

int partition(Comparable* A[], int left, int right, Comparable* pivot) {
  while (left <= right) { // Move bounds inward until they meet
    while (*A[left] < *pivot) left++;
    while ((right >= left)  && (*A[right] >= *pivot)) right--;
    if (right > left) swap(A, left, right);  // Swap out-of-place values
   }
  return left;           // Return first position in right partition
}

注意第二个内部 while 循环中对 right >= left 的检查。这确保了当枢轴是该分区中的最小值时， right 不会跑出分区的低端。函数 partition 返回右分区的第一个索引（即 left 结束的位置），以便确定对 qsort 进行递归调用时的子数组边界。

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

这里有一个可视化演示，用于说明分区函数的运行时间分析

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

11.3. 综合应用

这是整个快速排序算法的可视化演示。该可视化展示了由划分过程引起的逻辑分解是如何工作的。在可视化中，各个子分区被分开显示，以匹配递归树的结构。实际上，只涉及一个数组（正如您将在可视化之后的熟练度练习中看到的那样）。

这里有一个完整的熟练度练习，用于检验您对快速排序的理解程度。

11.4. 快速排序分析

此可视化解释了快速排序的最坏情况运行时间

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

这很糟糕，不比冒泡排序好。这种最坏情况何时会发生？只有当每个枢轴都导致数组的划分很差时才会发生。如果随机选择枢轴值，那么这种情况极不可能发生。当选择当前子数组的中间位置时，这种情况仍然不太可能发生。快速排序只需要少数几次良好的划分就能表现得相当不错。

此可视化解释了快速排序的最佳情况运行时间

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

快速排序的平均情况行为介于最坏情况和最好情况这两个极端之间。平均情况分析考虑所有可能输入排列的代价，将代价求和后除以情况总数。我们做一个合理的简化假设：在每次划分步骤中，枢轴元素同等可能地出现在（已排序）数组的任何位置。换句话说，枢轴元素同等可能地将数组划分为大小为 0 和 \(n-1\) ，或 1 和 \(n-2\) 等分区。

基于此假设，平均情况代价由以下方程计算得出：

\[{\bf T}(n) = cn + \frac{1}{n}\sum_{k=0}^{n-1}[{\bf T}(k) + {\bf T}(n - 1 - k)], \quad {\bf T}(0) = {\bf T}(1) = c.\]

此可视化将帮助你理解该递推关系是如何形成的。

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

这是一种平均情况代价与最坏情况代价具有不同渐近增长率的不寻常情况。考虑“平均情况”的实际含义。我们通过对大小为 \(n\) 的每个可能输入，将其运行时间代价乘以该输入出现的概率并求和，来计算大小为 \(n\) 的输入的平均代价。为简化问题，我们假设每个排列出现的可能性均等。因此，求平均值意味着对每个排列的代价求和，然后除以排列的数量（即 \(n!\) ）。我们知道其中一些 \(n!\) 个输入的代价为 \(O(n^2)\) 。但所有排列代价的总和必须为 \((n!)(O(n \log n))\) 。鉴于最坏输入极高的代价，这类输入的数量必然极少。事实上，代价为 \(O(n^2)\) 的输入不可能占据一个常数比例。即使只有 1% 的输入代价为 \(O(n^2)\) ，也会导致平均代价达到 \(O(n^2)\) 。因此，随着 \(n\) 的增长，高代价输入的比例必然趋近于零。我们可以得出结论：如果能避免那些极少的不良输入排列，快速排序将运行得很快。这就是选择一个好的枢轴如此重要的原因。

快速排序的运行时间可以得到改进（常数因子级别），并且已有大量研究致力于优化该算法。由于快速排序的最坏情况行为出现在枢轴未能将数组有效划分为等长子数组时，因此改进 findpivot 似乎是一个良好的起点。如果我们愿意投入更多工作来寻找更优的枢轴，不良枢轴的影响便可减弱甚至消除。希望由此节省的时间能够超过为寻找枢轴所增加的额外开销。一种广泛采用的选择是使用“三数取中”算法，即从三个随机选取的值中取其中间值作为枢轴。使用随机数生成器来选择位置相对耗时，因此常见的折衷方案是考察当前子数组的首位、中间位和末位。然而，我们简单的 findpivot 函数以中间值作为枢轴，其优点在于极不可能因偶然因素遇到不良输入，且实现成本很低。这与选择首记录或末记录作为枢轴形成鲜明对比，后者在许多近乎有序或近乎逆序的排列下会导致性能恶化。

通过认识到当 \(n\) 较小时快速排序相对较慢，可以显著改进性能。如果大多数时候我们对大型数组进行排序，这似乎并不相关；而且，在偶尔对小数组进行排序时，快速排序耗时多久也不应成为问题，因为无论如何它都会很快。但你应该注意到，快速排序本身会对许多许多小数组进行排序！这是分治法带来的自然副产品。

一个简单的改进方法可能是，当数据量较小时用更快的排序算法（如插入排序或选择排序）替换快速排序。然而，存在一种更好且更简单的优化方案：当快速排序的分区低于某个规模时，什么都不做！该分区内的值将是无序的。但是，我们知道数组中位于该分区左侧的所有值都小于分区内的所有值，而右侧的所有值都大于分区内的所有值。因此，即使快速排序仅将值移动到“近乎”正确的位置，数组也已接近有序。这正是利用插入排序（近乎）最佳情况性能的理想场景。最后一步是调用一次插入排序处理整个数组，从而将记录置于最终的有序状态。所使用的确切阈值取决于具体实现和运行环境的细节，但经验测试表明，当子数组缩小到大约 10-15 条记录时，应让其保持无序。

我们最后考虑的加速方案是降低递归调用的开销。快速排序本质上是递归的，因为每次快速排序操作都必须对两个子列表进行排序。因此，没有简单的方法将快速排序转换为迭代算法。然而，由于需要存储的信息量很小，快速排序可以使用栈来模拟递归。我们无需存储子数组的副本，只需存储子数组的边界即可。此外，如果注意执行快速排序递归调用的顺序，就可以保持较小的栈深度。我们还可以将 findpivot 和 partition 的代码内联，以消除剩余的函数调用。但请注意，如果不按上述建议处理小子列表，大约四分之三的函数调用就已经被消除了。因此，消除剩余的函数调用只会带来适度的加速。

以下是利用上述优化实现的快速排序示例代码。

// Optimized Quicksort: Not recursive, and uses Insertion sort for small lists
void quicksortOpt(int[] A, int oi, int oj) { // Quicksort
    int[] Stack = new int[MAXSTACKSIZE]; // Stack for array bounds
    int top = -1;
    int pivot;
    int pivotindex, l, r;

    Stack[++top] = oi;  // Initialize stack
    Stack[++top] = oj;

    while (top > 0) {   // While there are unprocessed subarrays
        // Pop Stack
        int j = Stack[top--];
        int i = Stack[top--];

        // Findpivot
        pivotindex = (i+j)/2;
        pivot = A[pivotindex];
        swap(A, pivotindex, j); // Stick pivot at end

        // Partition
        l = i-1;
        r = j;
        while (true) {
            while (A[++l] < pivot);
            while ((r!=0) && (A[--r] > pivot));
            if (l >= r) break;
            swap(A, l, r);
        }
        swap(A, l, j);  // Put pivot value in place

        // Put new subarrays onto Stack if they are small
        if ((l-i) > THRESHOLD) { // Left partition
            Stack[++top] = i;
            Stack[++top] = l-1;
        }
        if ((j-l) > THRESHOLD) { // Right partition
            Stack[++top] = l+1;
            Stack[++top] = j;
        }
    }
    inssort(A);                  // Final Insertion Sort
}

// Optimized Quicksort: Not recursive, and uses Insetion sort for small lists
void quicksortOpt(T[] A, int oi, int oj) { // Quicksort
    int[] Stack = new int[MAXSTACKSIZE]; // Stack for array bounds
    int listsize = oj-oi+1;
    int top = -1;
    T pivot;
    int pivotindex, l, r;

    Stack[++top] = oi;  // Initialize stack
    Stack[++top] = oj;

    while (top > 0) {   // While there are unprocessed subarrays
        // Pop Stack
        int j = Stack[top--];
        int i = Stack[top--];

        // Findpivot
        pivotindex = (i+j)/2;
        pivot = A[pivotindex];
        swap(A, pivotindex, j); // Stick pivot at end

        // Partition
        l = i-1;
        r = j;
        while (true) {
            while (A[++l].compareTo(pivot) < 0);
            while ((r!=0) && (A[--r].compareTo(pivot) > 0));
            if (l > r) break;
            swap(A, l, r);
        }
        swap(A, l, j);  // Put pivot value in place

        // Put new subarrays onto Stack if they are small
        if ((l-i) > THRESHOLD) {   // Left partition
            Stack[++top] = i;
            Stack[++top] = l-1;
        }
        if ((j-l) > THRESHOLD) {   // Right partition
            Stack[++top] = l+1;
            Stack[++top] = j;
        }
    }
    inssort(A);                    // Final Insertion Sort
}

待处理

type: Exercise

考虑本模块的快速排序实现，其中枢轴选择为划分部分的中间值。给出一个 0 到 7 的排列，使快速排序表现出最坏情况行为。

存在多种可能的正确答案。为了评估该答案，需要在学生的分区上运行 Quicksort，并验证每一步是否都会生成大小为 6、5、4、3、2，然后是 1 的新分区。

   «  10. 实现归并排序   ::   目录   ::   12. 堆排序  »

© Copyright 2011-2025 by OpenDSA Project Contributors and distributed under an MIT license. 最后更新于 9月 30, 2026. Created using Sphinx 8.2.0.
关闭窗口