图解排序算法（五）之快速排序——三数取中法

快速排序（Quick Sort）是计算机科学中最经典、应用最广泛的排序算法之一，由 Tony Hoare 在 1960 年提出。其核心思想是分而治之（Divide and Conquer），通过一趟排序将待排序列分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据小，然后再按此方法对这两部分数据分别进行快速排序，整个过程可以递归进行，以此达到整个数据变成有序序列。

然而，基础的快速排序有一个致命的弱点：对输入数据的顺序非常敏感。当待排序序列已经基本有序或完全逆序时，快速排序的效率会退化为 O(n²)，这与简单的冒泡排序无异。

为了解决这个问题，业界提出了多种优化方案，其中三数取中法（Median-of-Three） 是最有效、最简单的方法之一。本文将深入剖析快速排序的原理，并重点图解如何使用三数取中法来优化分区过程，确保算法在绝大多数情况下都能保持高效的 O(n log n) 时间复杂度。

作者：dreamcatcher 原文链接：[您的博客链接] 版权声明：转载请注明出处

目录#

  1. 快速排序基础原理
    1. 算法思想
    2. 基准值（Pivot）的选择
    3. 单趟排序（Partition）过程
  2. 为什么需要优化？—— 基础快速排序的弱点
  3. 三数取中法（Median-of-Three）详解
    1. 什么是三数取中法？
    2. 三数取中法的步骤
    3. 结合三数取中法的 Partition 过程
  4. 算法实现（Java代码）
  5. 复杂度分析
  6. 总结与最佳实践
  7. 参考资料

一、快速排序基础原理#

算法思想#

快速排序的算法思想可以概括为以下三步：

  1. 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot）。
  2. 分区操作：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
  3. 递归排序：递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。

基准值（Pivot）的选择#

基准值的选择至关重要，它直接影响分区的平衡度，进而影响算法效率。常见的选择方式有：

  • 固定选择：总是选择第一个元素或最后一个元素。这是最简单的方式，但在处理有序数组时效率会急剧下降。
  • 随机选择：随机从数组中选取一个元素作为基准。这是一种很好的优化，能有效避免最坏情况的发生。
  • 三数取中法：本文的重点，它是对固定选择的一种有效改进。

单趟排序（Partition）过程#

这是快速排序的核心。我们以最经典的 Lomuto分区方案 为例，选择最后一个元素为基准。

假设我们对数组 arr = [3, 7, 8, 5, 2, 1, 9, 5, 4] 进行排序，选择最后一个元素 4 作为基准。

图解过程：

  1. 初始化：设定一个指针 i，初始为 low - 1（即 -1）。它的意义是“小于基准的子数组的最后一个元素的索引”。我们从 low 到 high-1 遍历数组。

    索引:  0   1   2   3   4   5   6   7   8
数组: [3,  7,  8,  5,  2,  1,  9,  5,  4]
      i

  2. 遍历与交换：

    • j=0, 元素 3 < 4。i++（i 变为 0），交换 arr[i] 和 arr[j]（自己和自己交换，无变化）。此时，[3] 是小于基准的区域。
    • j=1, 元素 7 > 4。不做任何操作，i 不动。
    • j=2, 元素 8 > 4。不做任何操作。
    • j=3, 元素 5 > 4。不做任何操作。
    • j=4, 元素 2 < 4。i++（i 变为 1），交换 arr[1]（7） 和 arr[4]（2）。 
      数组变为: [3,  2,  8,  5,  7,  1,  9,  5,  4]
    • j=5, 元素 1 < 4。i++（i 变为 2），交换 arr[2]（8） 和 arr[5]（1）。 
      数组变为: [3,  2,  1,  5,  7,  8,  9,  5,  4]
    • j=6, 元素 9 > 4。不做任何操作。
    • j=7, 元素 5 > 4。不做任何操作。

  3. 放置基准：遍历结束后，i 现在指向最后一个小于基准的元素（索引 2，值为 1）。我们将基准 arr[high]（4） 与 arr[i+1]（5） 交换，将基准放到正确的位置。

    交换 arr[3] 和 arr[8]： [3,  2,  1,  4,  7,  8,  9,  5,  5]

    现在，基准 4 左边的 [3, 2, 1] 都小于它，右边的 [7, 8, 9, 5, 5] 都大于等于它。

动画示意： [3, 7, 8, 5, 2, 1, 9, 5, 4] -> 遍历交换 -> [3, 2, 1, 5, 7, 8, 9, 5, 4] -> 放置基准 -> [3, 2, 1, 4, 7, 8, 9, 5, 5]

二、为什么需要优化？—— 基础快速排序的弱点#

假设我们使用基础快速排序（总是选择第一个元素为基准）对一個已经升序排列的数组 [1, 2, 3, 4, 5, 6, 7, 8] 进行排序：

  • 第一趟：基准是 1，小于 1 的区域为空，大于 1 的区域是 [2, 3, 4, 5, 6, 7, 8]。分区极度不平衡。
  • 第二趟：对 [2, 3, 4, 5, 6, 7, 8] 排序，基准是 2，同样，分区结果是一边倒。
  • ... 以此类推。

你会发现，每次分区都只能将问题规模减少 1，递归树的高度变成了 n，而每层分区操作的时间是 O(n)，所以总时间复杂度退化为 O(n²)。

根本原因：固定的基准选择策略在遇到有序序列时，无法产生平衡的分区。

三、三数取中法（Median-of-Three）详解#

什么是三数取中法？#

三数取中法的核心思想是：不直接使用序列的头或尾作为基准，而是选取头、中、尾三个元素中的中位数作为基准。

例如，对于序列 [8, 1, 4, 9, 6, 3, 5, 2, 7, 0]：

  • 头元素：8
  • 中元素：6（索引在中间）
  • 尾元素：0 这三个数的中位数是 6。我们选择 6 作为基准。

这样做的好处是，可以有效地避免选取到序列中的最大值或最小值作为基准，从而大大增加分区平衡的可能性。

三数取中法的步骤#

假设当前待排序子数组的区间是 [low, high]。

  1. 计算中间索引：mid = low + (high - low) / 2。（注意：使用此公式可以防止 (low + high) 可能出现的整数溢出）
  2. 比较三个数：比较 arr[low]、arr[mid]、arr[high] 的大小。
  3. 交换确保顺序：通过几次交换，将这三个数排成 arr[low] <= arr[mid] <= arr[high] 的顺序。此时，中位数就是 arr[mid]。
  4. 将中位数交换到候选位置：通常，我们将这个中位数（arr[mid]）与 arr[low] 或 arr[high-1] 交换，使其在后续的 Partition 过程中被选为基准。这样做可以将中位数“藏”在一个安全的位置，同时简化 Partition 的边界处理。

结合三数取中法的 Partition 过程#

我们通常将三数取中法与 Hoare分区方案 或经过调整的 Lomuto 方案结合。这里介绍一种常见且高效的做法：

  1. 三数取中并交换：对 arr[low], arr[mid], arr[high] 排序，并将中位数交换到 arr[low] 的位置。现在，arr[low] 就是一个比较合理的基准值。
  2. 进行标准 Partition：以 arr[low] 为基准，使用 Hoare 或 Lomuto 方法进行分区。

图解示例： 对 arr = [9, 2, 5, 1, 7, 6, 3, 8, 4] 进行第一趟排序，low=0, high=8。

  1. 取中：
    • low=0 -> 9
    • mid=4 -> 7
    • high=8 -> 4
    • 排序这三个数：4, 7, 9。中位数是 7。
  2. 交换：将中位数 7（原在 mid=4 位置）与 arr[low]（9） 交换。 
    原数组: [9, 2, 5, 1, 7, 6, 3, 8, 4]
交换后: [7, 2, 5, 1, 9, 6, 3, 8, 4]
    现在，基准值 7 位于数组开头。
  3. Partition：以 7 为基准进行分区（例如使用Hoare法）。
    • 从左找大于 7 的数（9），从右找小于 7 的数（4）。
    • 交换 9 和 4：[7, 2, 5, 1, 4, 6, 3, 8, 9]
    • 继续，左指针找到 8，右指针找到 3（8 和 3 已经交错），循环结束。
    • 最后将基准 7 与右指针所在位置（index=6, 值 3）交换：[3, 2, 5, 1, 4, 6, 7, 8, 9] 分区完成，基准 7 左边都小于它，右边都大于它。

可以看到，分区结果相当平衡。

四、算法实现（Java代码）#

以下是使用三数取中法优化，并结合 Hoare 分区方案的快速排序实现。

public class QuickSortMedianOfThree {
 
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }
 
    private static void quickSort(int[] arr, int low, int high) {
        // 使用插入排序优化小数组
        if (high - low + 1 < 10) {
            insertionSort(arr, low, high);
            return;
        }
 
        if (low < high) {
            // 获取分区索引，pivot 已在其正确位置
            int pivotIndex = partition(arr, low, high);
            // 递归排序左半部分
            quickSort(arr, low, pivotIndex - 1);
            // 递归排序右半部分
            quickSort(arr, pivotIndex + 1, high);
        }
    }
 
    private static int partition(int[] arr, int low, int high) {
        // 1. 三数取中法选取基准，并将其交换到 low 位置
        medianOfThree(arr, low, high);
        int pivot = arr[low]; // 现在 pivot 是左、中、右的中位数
 
        // 2. Hoare 分区算法
        int i = low - 1;
        int j = high + 1;
 
        while (true) {
            // 从左向右找到第一个大于等于 pivot 的元素
            do {
                i++;
            } while (arr[i] < pivot);
 
            // 从右向左找到第一个小于等于 pivot 的元素
            do {
                j--;
            } while (arr[j] > pivot);
 
            // 如果指针相遇，分区结束
            if (i >= j) {
                return j; // 返回右指针的位置作为新的分界
            }
 
            // 交换两个逆序元素
            swap(arr, i, j);
        }
    }
 
    /**
     * 三数取中法，并将中位数交换到 arr[low] 的位置
     */
    private static void medianOfThree(int[] arr, int low, int high) {
        int mid = low + (high - low) / 2;
 
        // 保证 arr[low] <= arr[mid]
        if (arr[low] > arr[mid]) {
            swap(arr, low, mid);
        }
        // 保证 arr[low] <= arr[high]
        if (arr[low] > arr[high]) {
            swap(arr, low, high);
        }
        // 保证 arr[mid] <= arr[high]（此时 arr[low] 已经是三个数中最小的）
        if (arr[mid] > arr[high]) {
            swap(arr, mid, high);
        }
 
        // 将中位数（arr[mid]）交换到 low 位置，作为后续的基准
        swap(arr, low, mid);
    }
 
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
    // 用于优化小数组的插入排序
    private static void insertionSort(int[] arr, int low, int high) {
        for (int i = low + 1; i <= high; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= low && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
 
    // 测试代码
    public static void main(String[] args) {
        int[] arr = {3, 7, 8, 5, 2, 1, 9, 5, 4};
        System.out.println("排序前: " + Arrays.toString(arr));
        quickSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

五、复杂度分析#

  • 时间复杂度：
    • 平均情况：O(n log n)。三数取中法极大地提高了分区的平衡性，使得递归树的高度接近 log n。
    • 最坏情况：O(n²)。尽管三数取中法使得最坏情况极难出现（除非每次取到的中位数都是极端值），但理论上依然存在。结合随机化可以完全避免。
  • 空间复杂度：O(log n)。主要是递归调用栈的深度。

六、总结与最佳实践#

三数取中法是一种简单而强大的优化策略，它通过一个微小的预处理步骤，显著提升了快速排序在真实场景下的稳定性和性能。

快速排序的最佳实践总结：

  1. 总是使用三数取中法：这是避免最坏情况、提升平均性能性价比最高的方法。
  2. 小数组使用插入排序：当递归到子数组规模较小（例如长度 < 10）时，快速排序的递归开销变得显著。此时切换成插入排序等简单排序算法，可以带来明显的性能提升。
  3. 考虑使用迭代代替递归：对于深度递归可能引发栈溢出的场景，可以使用栈（Stack）来模拟递归过程，实现迭代版的快速排序。
  4. 处理大量重复元素：如果数组中存在大量重复元素，标准的快速排序效率也会下降。可以考虑使用三路快速排序，将数组分为“小于、等于、大于”基准三部分，能高效处理重复元素。

总而言之，基础快速排序 + 三数取中法 + 小数组插入排序 是一个在工程实践中非常经典、高效且稳定的排序算法组合。

参考资料#

  1. Hoare, C. A. R. (1961). Algorithm 64: Quicksort. Communications of the ACM, 4(7), 321.
  2. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley Professional.
  3. Knuth, D. E. (1997). The Art of Computer Programming, Volume 3: Sorting and Searching (3rd ed.). Addison-Wesley.
  4. 快速排序 - 维基百科
  5. Visualgo.net - 排序算法可视化

免责声明：本文部分图示和代码示例为便于理解进行了简化，在实际生产环境中请结合具体场景进行测试和优化。

2026-03