排序算法之：多路快速排序（Multiway Quicksort）的递归分区策略与性能分析 今天我们来讲解一个快速排序的高级变体： 多路快速排序 。它是对经典快速排序的泛化，从每次划分将数组分为两部分（通常称为“二路划分”或“双路划分”），扩展为每次划分将数组分为多个部分（K路，K>=2）。我们将从问题描述、算法思想、递归分区策略、性能分析以及示例演示等步骤，循序渐进地进行讲解。 1. 问题描述 给定一个包含n个可比较元素的数组（例如整数），我们需要将其按非递减顺序排序。 多路快速排序 的目标是，在每次递归分区时，不是选择一个主元（pivot）将数组划分为“小于主元”和“大于等于主元”的两部分，而是选择 多个主元 ，将数组划分为K+1个部分（K个主元），使得： 第一部分的所有元素 < 第一个主元 第二部分的所有元素等于第一个主元 第三部分的所有元素在（第一个主元, 第二个主元）之间 依此类推... 最后一部分的所有元素 > 最后一个主元 之后，递归地对那些 包含多个不同元素 的部分进行排序。这种划分方式可以更精细地切分数据，理论上能减少递归深度和比较次数，尤其在数据分布具有多个聚类时表现更好。 2. 算法思想与核心步骤 多路快速排序的核心在于 递归分区策略 。我们以 三路快速排序 （K=2）为例，因为它是最常见且易于理解的多路划分。之后我们会将其泛化到K>2的情况。 2.1 三路快速排序（K=2） 在三路划分中，我们选择 两个主元 （通常记为pivot1和pivot2，且pivot1 <= pivot2）。划分后，数组被分为三个部分： 小于pivot1的部分 在pivot1和pivot2之间的部分（包含等于pivot1或pivot2的元素，但通常我们进一步细化处理） 大于pivot2的部分 但实际上，更经典的三路划分是“荷兰国旗问题”的变体，它通过 一次遍历 将数组分为三部分：小于pivot、等于pivot、大于pivot。这里的pivot是单个主元。为了与多路划分（K>1）区分，我们将其视为K=1的一种特殊多路划分（即双路划分的扩展，但主元只有一个）。 真正意义上的K=2（双主元） 需要更复杂的划分逻辑。我们以K=2为例说明多路划分的一般步骤： 选择主元 ：从数组中选取两个元素作为主元pivot1和pivot2。为确保划分平衡，通常采用随机选择或“三数取中”等策略，并确保pivot1 <= pivot2（如果不是，则交换它们）。 初始化指针 ：设立多个指针来标记不同部分的边界。对于K=2，我们需要划分出4个部分（K+1=3个区间，但因为包含等于主元的情况，实际上可能有5个部分，但为了简化，我们通常将等于主元的元素归入相邻区间）。更通用的方法是使用 K+1个指针 ，但实现上更常用 三个指针进行一次扫描 ，具体如下： 设置指针： low 指向数组起始， high 指向数组末尾， i 从 low 开始扫描。 当 i <= high 时： a. 如果 arr[i] < pivot1 ，交换 arr[i] 和 arr[low] ，然后 low++ , i++ 。 b. 如果 arr[i] > pivot2 ，交换 arr[i] 和 arr[high] ，然后 high-- （注意：此时不增加 i ，因为交换过来的新元素还未检查）。 c. 否则（即 pivot1 <= arr[i] <= pivot2 ）， i++ 。 递归排序 ：划分结束后，我们得到三个部分： [start, low-1] ：所有小于pivot1的元素。 [low, high] ：所有在pivot1和pivot2之间（含等于）的元素。 注意 ：这个区间可能已经有序（因为所有元素都落在[ pivot1, pivot2 ]区间内），但通常我们仍需递归排序，除非区间内所有元素都相等（可跳过）。 [high+1, end] ：所有大于pivot2的元素。 对第一部分和第三部分递归进行多路快速排序。 2.2 泛化到K路（K>2） 对于一般的K，我们需要选择K个主元（pivot1 <= pivot2 <= ... <= pivotK）。划分目标是将数组分为K+1个部分： 部分0: 所有元素 < pivot1 部分1: 所有元素 = pivot1 部分2: 所有元素在 (pivot1, pivot2) 之间 ... 部分2K-1: 所有元素 = pivotK 部分2K: 所有元素 > pivotK 实际上，为了简化，我们常将“等于主元”的元素合并到相邻区间，因此只需K+1个部分。划分过程可以通过 多次扫描 或 使用多个指针一次扫描 实现，但复杂度会增加。一种常见方法是： 用某种排序（如插入排序）对K个主元进行排序，得到有序主元序列。 遍历数组元素，通过 二分查找 确定每个元素应落入哪个区间（即找到第一个大于该元素的主元位置）。 将元素分配到对应的临时桶中，然后回写到原数组，形成K+1个连续区间。 递归地对每个非空且包含多个不同值的区间进行排序。 3. 详细步骤与示例 我们以K=2（双主元）为例，用一个具体数组演示划分过程。 示例数组 ： [9, 3, 7, 2, 8, 5, 1, 4, 6] 假设我们随机选择两个主元：选择索引2和6的元素，即 arr[2]=7 和 arr[6]=1 。排序主元：pivot1=1, pivot2=7。 初始化： low = 0 , high = 8 , i = 0 数组： [9, 3, 7, 2, 8, 5, 1, 4, 6] i=0, arr[ 0]=9 > pivot2=7 → 交换arr[ 0]和arr[ 8], high-- → [6, 3, 7, 2, 8, 5, 1, 4, 9] , i不变 i=0, arr[ 0]=6, pivot1=1 <= 6 <= pivot2=7 → i++ → i=1 i=1, arr[ 1]=3, 1<=3 <=7 → i++ → i=2 i=2, arr[ 2 ]=7, 等于pivot2 → i++ → i=3 i=3, arr[ 3]=2, 1<=2 <=7 → i++ → i=4 i=4, arr[ 4]=8 > pivot2=7 → 交换arr[ 4]和arr[ 7], high-- → [6, 3, 7, 2, 4, 5, 1, 8, 9] , i不变 i=4, arr[ 4]=4, 1<=4 <=7 → i++ → i=5 i=5, arr[ 5]=5, 1<=5 <=7 → i++ → i=6 i=6, arr[ 6]=1, 等于pivot1 → 交换arr[ 6]和arr[ low] (low=0), low++ → [1, 3, 7, 2, 4, 5, 6, 8, 9] , i++ → i=7 i=7, arr[ 7]=8 > pivot2=7 → 交换arr[ 7]和arr[ high ] (high=6), high-- → 此时high=5, i=7 > high, 循环结束。 划分结果： 小于pivot1的部分：索引0~low-1，即[ 0, -1 ]（空） 中间部分：索引low~high，即[ 0, 5] → [1, 3, 7, 2, 4, 5, 6] （注意：这个区间包含小于、等于、大于主元的混合，因为我们简化了逻辑，实际上它包含所有在[ pivot1, pivot2 ]之间的元素，但pivot1=1, pivot2=7，而2,3,4,5,6都在其中，7等于pivot2，1等于pivot1。但1在区间最左，7在中间，并不完全有序） 大于pivot2的部分：索引high+1~end，即[ 6, 8] → [8, 9] 接下来，我们需要 对中间部分进一步排序 ，因为它包含多个不同值。这可以通过递归调用多路快速排序（选择新的主元）完成。最终，通过递归，整个数组被排序。 4. 性能分析 时间复杂度 ： 最佳情况：每次划分都能将数组均匀分成K+1份，递归深度为O(log_ {K+1} n)，每层比较次数为O(n)（每个元素与K个主元比较，K视为常数），总时间复杂度为O(n log n)。 最坏情况：每次划分都极不均匀，例如所有元素都落入同一个区间，退化为O(n^2)。但通过随机选择主元，可使得期望时间复杂度为O(n log n)。 平均情况：O(n log n)，但常数因子比经典快速排序大，因为每个元素需要与K个主元比较（虽然K是常数，但增加了比较次数）。 空间复杂度 ： 递归调用栈深度为O(log n)（平均），最坏O(n)。如果使用就地划分，额外空间为O(1)（不包括递归栈）。如果使用辅助数组进行划分，则需要O(n)额外空间。 优势 ： 当数据中存在多个自然聚类时，多路划分能更高效地分离这些聚类，减少递归深度。 对于包含大量重复元素的数组，多路划分（特别是将等于主元的元素单独分离）能避免不平衡划分，提高效率。 劣势 ： 实现复杂，容易出错。 选择多个主元的开销较大，如果主元选择不当，可能导致性能下降。 5. 总结 多路快速排序是快速排序的泛化，通过使用多个主元进行更精细的划分，可能在某些数据分布上获得性能提升。然而，由于实现复杂性和常数因子较大，在实践中， 双轴快速排序 （K=2的一种高效实现，如Java的Arrays.sort()所用）是更常见的变体，而K>2的多路划分则较少使用，因为收益与开销往往不成正比。 理解多路快速排序的关键在于掌握其递归分区策略，以及如何通过指针操作在一次遍历中完成多路划分。这有助于深化对分治策略和快速排序变体的认识。