快速排序与归并排序 | AI生成和翻译
为什么快速排序让人感觉棘手（而归并排序不会）
你说得对——不参考资料直接手写快速排序就像在抓抹了油的猪，而归并排序则更像叠衣服：有条不紊且可预测。归并排序的”分治合”流程是线性且递归清晰的，合并步骤中没有任何意外。而快速排序是原地排序，依赖围绕”枢轴”（选定的分割点）交换元素的巧妙分区技巧。最初会感觉混乱，因为枢轴并不固定——更像是在游戏中不断被移动的裁判。但一旦领悟其精髓，就会感受到它优雅的效率（平均时间复杂度O(n log n)，最坏情况下若枢轴选择不当则为O(n²)）。
让我用一个自然的、故事化的视角介绍快速排序：想象按高度整理书架上杂乱堆放的书籍。你不是将书堆对半分开、逐本测量再合并（那是归并排序），而是选一本书作为”基准”（枢轴），然后重新排列其他书，使所有更矮的书位于其左侧，更高的书位于其右侧。枢轴最终会落在它的最终位置，你只需递归处理左右两个子书堆。无需额外空间——只需在书架上交换位置。这就像荷兰的”快速排序”升旗仪式（因此得名），将元素划分为三组：较矮组、基准组、较高组。
原理剖析：分区的魔力
快速排序之所以有效，在于带有保证的分治策略：每个分区步骤至少将一个元素（枢轴）放置在其正确的最终位置，每次至少缩小这么大规模的问题。最佳情况下，枢轴将数组均匀分割（如归并排序的对半分割），形成平衡的递归。最坏情况下（例如已排序数组搭配糟糕的枢轴选择），它会退化为O(n²)，类似冒泡排序——但良好的枢轴选择策略使其在实践中速度极快。
关键洞见在于：分区强制执行不变性。一次分区后：
- 枢轴左侧的所有元素 ≤ 枢轴。
- 枢轴右侧的所有元素 ≥ 枢轴。
- 枢轴此刻已彻底排序完毕——无需再次移动。
这保证了进展：递归树的深度平均最多为log n，每层总共进行O(n)次操作（扫描和交换）。
如何选择枢轴（以及为什么它在比较过程中会”移动”）
枢轴并非神圣不可移动——它只是你选择用来作为基准的任意元素。糟糕的选择（比如总是选第一个元素）可能导致失衡，以下是从简单到稳健的策略演进：
- 朴素策略：选择首元素（或尾元素）
- 编码简单但有风险。在已排序数组
[1,2,3,4,5]中，枢轴=1意味着左侧为空，右侧有4个元素——递归严重失衡。 - “移动”原理：在分区过程中，你将其他所有元素与此枢轴值比较，但交换的是围绕其位置的元素。当边界跨越枢轴时，枢轴本身会被交换到正确位置。
- 编码简单但有风险。在已排序数组
- 改进策略：选择中间元素
- 先将其临时交换至末尾，作为枢轴使用。直观上更平衡（更接近中位数），但仍可能受已排序/逆序输入的影响。
- 实践最佳：随机选择一个元素
- 将其交换至末尾后进行分区。随机性平均掉了糟糕情况，使得最坏情况极不可能发生（以高概率保持O(n log n)）。这是大多数库函数采用的方法。
- 进阶技巧（适用于面试）：三数取中法
- 选择首元素、中间元素、尾元素的中位数作为枢轴。计算快速，能规避常见陷阱。
在代码中，你通常通过先将枢轴交换至末尾来”固定”它，围绕其值（而非位置）进行分区，最后再将其交换回归属位置。这就是为什么枢轴感觉在”移动”——它并非静止；分区过程通过两个相向跳跃的指针（左指针和右指针）动态地找到其位置，并交换违规元素。
动手示例：使用尾元素作为枢轴排序 [3, 7, 1, 9, 4]
让我们一步步演示分区过程。数组：[3, 7, 1, 9, 4]。枢轴 = 尾元素 = 4。（我们将根据需要交换其位置。）
- 左指针始于索引0（值3），右指针始于索引3（值9，因为枢轴在索引4）。
- 从左扫描：3 < 4？是，保留。下一个，7 > 4？是，但等等——我们将其与右侧首个>4的元素交换。
- 实际上，标准的Lomuto分区（单指针风格）：
- i = -1（作为 < 枢轴的边界）。
- 对于 j 从 0 到 n-2（跳过枢轴）：
- 如果 arr[j] ≤ 枢轴 (4)，交换 arr[++i] 与 arr[j]。（扩展左侧区域。）
- 最后，将枢轴与 arr[++i] 交换以放置它。
逐步过程：
- j=0：3 ≤4？是。i=0，交换 arr[0] 与 arr[0]（无变化）。数组：[3,7,1,9,4]
- j=1：7 ≤4？否。跳过。
- j=2：1 ≤4？是。i=1，交换 arr[1] (7) 与 arr[2] (1)。数组：[3,1,7,9,4]
- j=3：9 ≤4？否。跳过。
- 结束：交换枢轴 (4，在索引4) 与 arr[++i=2] (7)。数组：[3,1,4,9,7]
现在：4（索引2）的左侧是[3,1]（均≤4，未排序），右侧是[9,7]（均≥4，未排序）。枢轴=4已排序完成。递归处理左侧[3,1]和右侧[9,7]。
- 左侧：枢轴=1，分区为[1,3]。
- 右侧：枢轴=7，分区为[7,9]。
完全排序后：[1,3,4,7,9]。看到了吗？每一步都锁定进展，交换操作将枢轴”移动”到位。
伪代码概览（助你轻松实现）
quicksort(arr, low, high):
若 low < high:
pivot_idx = partition(arr, low, high)
quicksort(arr, low, pivot_idx-1)
quicksort(arr, pivot_idx+1, high)
partition(arr, low, high): # Lomuto风格，枢轴在high
pivot = arr[high]
i = low - 1
对于 j 从 low 到 high-1:
若 arr[j] <= pivot:
i += 1
交换 arr[i] 与 arr[j]
交换 arr[i+1] 与 arr[high]
返回 i+1
“移动”发生在这些交换中：元素相互穿插移动，直至枢轴落定。用纸笔以5-6个元素练习——一旦理解分区，递归就会显得自然。若遇障碍，尝试在脑海中将其动画化为整理书架的过程。
深入探索：
快速排序可视化
CLRS 快速排序章节