快速排序Quick Sort是排序算法中概念清晰、实现却很考验细节的一类算法。它常常被用于教学演示也因为平均时间复杂度为 (O(n \log n))、额外空间占用小成为很多标准库排序实现的重要基础。可不少学习者背下代码后一旦换一种基准选择方式或者换一组含大量重复元素的数组程序就会出现排序错误甚至栈溢出。要真正掌握快速排序最有效的办法不是死记递归代码而是先把“分区Partition”过程在脑中完整推演一遍再去看代码每一步对应的动作。这篇文章会用适合动画讲解的方式拆解快速排序先讲清楚分治和基准之间的关系再用一个具体数组逐步演示指针移动、交换和递归调用过程最后给出 Java、C 和 Python 的参考实现并补充常见错误排查、性能分析和工程优化建议。如果你正在准备算法面试或者想亲手实现一个能放进项目里的排序工具这篇文章可以当作从理解到落地的完整笔记。1. 快速排序真正在解决什么分治思想下的基准归位快速排序的核心不是“把整个数组一次排好”而是每次只解决一个元素的最终位置问题。选中数组中的某个值作为基准pivot经过一趟分区后所有小于基准的值都放到基准左边所有大于基准的值都放到基准右边。此时基准已经处于整个数组排序后的正确位置它不需要再参与后续移动。这个过程要反复递归执行。左边的子数组做一次快速排序右边的子数组再做一次快速排序直到每个子数组的长度为 0 或 1。整体思路来自分治法把大问题拆成两个规模更小、互相独立的小问题。1.1 分区操作是整个算法的心脏排序是否正确代码是否能终止基本都被分区这一步决定。常见的分区方式有两种一种是 Lomuto 分区使用单向指针从左向右扫描逻辑直观适合教学和入门实现。另一种是 Hoare 分区使用左右两个指针向中间靠近交换次数通常更少效率更高但边界条件更难写对。两种分区的共同目标只有一个经过一轮数组遍历后返回基准元素的下标并确保基准左侧不大于基准、右侧不小于基准。1.2 稳定性和原地排序要先分清排序算法有两个常用判断标准是否稳定是否原地排序。稳定指的是排序前后相等元素的相对顺序不被改变。快速排序分区时会交换相隔较远的元素因此不是稳定排序。原地排序指的是排序过程中不需要申请额外的大块内存主要借助原数组交换元素完成。快速排序通常是原地排序但递归调用会消耗函数调用栈空间这一点在生产环境里值得注意。对于双关键字排序等需要保留原始先后顺序的场景例如先按时间再按优先级排序快速排序不能直接依赖应使用归并排序等稳定排序算法。2. 把快速排序当动画看一次完整的分区推演动画或者图示之所以能帮助理解是因为排序本质上就是一系列状态变化。我们需要观察的变量只有几个当前子数组的范围、基准的值、扫描指针的位置以及发生交换的时刻。下面以数组作为示例[5, 1, 9, 3, 6, 2, 7, 4]采用 Lomuto 分区暂时固定选择最右侧元素作为基准。选择最右侧元素是为了代码简单教学演示时最容易跟踪但它不是工程上最好的选择后文会单独分析。2.1 先定义两个指针的含义Lomuto 分区需要两个变量i最后一个“已经确认小于基准”的元素所在下标初始为left - 1。j当前扫描指针从left向right - 1移动。每次当array[j] pivot时先把i向后移动一位再交换array[i]和array[j]。这样做的效果是把小于基准的值不断往数组左侧堆放。一趟扫描结束后所有小于基准的值都集中在i及其左侧。把基准和array[i 1]交换基准就回到了最终位置分区结束。2.2 逐轮观察指针和数组变化对于数组[5, 1, 9, 3, 6, 2, 7, 4]最右侧基准是4。初始i -1 j 0扫描 5 5 4 不成立不交换j 1扫描 1 1 4 成立 i 变为 0 交换 array[0] 和 array[1] 数组变为[1, 5, 9, 3, 6, 2, 7, 4]j继续向后扫描j 2扫描 9 9 4 不成立 j 3扫描 3 3 4 成立 i 变为 1 交换 array[1] 和 array[3] 数组变为[1, 3, 9, 5, 6, 2, 7, 4]继续扫描j 4扫描 6 6 4 不成立 j 5扫描 2 2 4 成立 i 变为 2 交换 array[2] 和 array[5] 数组变为[1, 3, 2, 5, 6, 9, 7, 4]j 6扫描 7 7 4 不成立 扫描结束此时i 2array[i 1] array[3] 5。把基准4与5交换得到[1, 3, 2, 4, 6, 9, 7, 5]返回基准下标3。从这一刻开始数字4已经处在最终正确位置左边的[1, 3, 2]都小于 4右边的[6, 9, 7, 5]都大于 4。2.3 观察动画时要抓住哪些关键点看快速排序动画时不建议只关注最后的排序结果而是按以下顺序观察当前这一段子数组的left和right边界在哪里。选中的基准原先是哪个位置的值。扫描过程中发生了哪几次交换。分区结束后基准落在哪个下标。递归进入哪两个子问题顺序是什么。动画的价值在于把“数组下标变化”变成可视状态。如果只看代码容易忽略递归区间为何不能包含刚刚返回的基准。看动画时容易明白基准已经归位左右两侧互相独立不能再把基准放入任何一侧的递归范围。2.4 第一轮结束后递归如何继续第一轮分区的结果是下标3上的4已经归位。接下来快速排序分别处理左子数组[1, 3, 2] 右子数组[6, 9, 7, 5]左子数组递归时边界是原数组下标0到2右子数组递归时边界是原数组下标4到7。如果代码写成把4再次包含进某一边结果不会立刻报错但会导致递归无法收敛最终出现栈溢出。这是快速排序初学阶段最典型的问题之一。3. 从推演到代码Java 和 C 的参考实现动画推演已经明确了分区的动作。写成代码时关键是保证变量含义和推演时保持一致。3.1 Java 实现从分区函数开始写先写分区函数。这里固定选择最右侧元素作为基准是为了让代码和上面推演完全对应。public class QuickSortDemo { public static void quickSort(int[] array, int left, int right) { if (left right) { return; } int pivotIndex partition(array, left, right); quickSort(array, left, pivotIndex - 1); quickSort(array, pivotIndex 1, right); } private static int partition(int[] array, int left, int right) { int pivot array[right]; int i left - 1; for (int j left; j right; j) { if (array[j] pivot) { i; swap(array, i, j); } } swap(array, i 1, right); return i 1; } private static void swap(int[] array, int indexA, int indexB) { int temp array[indexA]; array[indexA] array[indexB]; array[indexB] temp; } public static void main(String[] args) { int[] sample {5, 1, 9, 3, 6, 2, 7, 4}; System.out.print(排序前: ); printArray(sample); quickSort(sample, 0, sample.length - 1); System.out.print(排序后: ); printArray(sample); } private static void printArray(int[] array) { for (int value : array) { System.out.print(value ); } System.out.println(); } }这段代码的关键点在quickSort的递归边界。partition返回pivotIndex后左侧递归范围是left到pivotIndex - 1右侧递归范围是pivotIndex 1到right。基准位置本身不再进入递归。3.2 C 语言实现保持相同逻辑C 语言版本和 Java 版本几乎完全一致只是数组传入方式不同。完整代码如下#include stdio.h void swap(int array[], int indexA, int indexB) { int temp array[indexA]; array[indexA] array[indexB]; array[indexB] temp; } int partition(int array[], int left, int right) { int pivot array[right]; int i left - 1; for (int j left; j right; j) { if (array[j] pivot) { i; swap(array, i, j); } } swap(array, i 1, right); return i 1; } void quickSort(int array[], int left, int right) { if (left right) { return; } int pivotIndex partition(array, left, right); quickSort(array, left, pivotIndex - 1); quickSort(array, pivotIndex 1, right); } void printArray(int array[], int size) { for (int i 0; i size; i) { printf(%d , array[i]); } printf(\n); } int main() { int sample[] {5, 1, 9, 3, 6, 2, 7, 4}; int size sizeof(sample) / sizeof(sample[0]); printf(排序前: ); printArray(sample, size); quickSort(sample, 0, size - 1); printf(排序后: ); printArray(sample, size); return 0; }在 C 语言环境中要注意原数组通过引用传递递归函数里的交换直接作用在原数组上不需要额外返回数组。如果从partition返回的是数组而不是下标说明概念上还没完全切换过来。3.3 Python 简洁写法便于理解但和原地版本不同Python 也可以写出非常适合表达的版本。下面的写法返回新数组不对原数组原地修改教学方便但生产使用时要注意它会产生多个新列表def quick_sort(nums): if len(nums) 1: return nums pivot nums[len(nums) // 2] left [x for x in nums if x pivot] middle [x for x in nums if x pivot] right [x for x in nums if x pivot] return quick_sort(left) middle quick_sort(right) sample [5, 1, 9, 3, 6, 2, 7, 4] print(排序前:, sample) print(排序后:, quick_sort(sample))这个版本把小于、等于、大于基准的元素拆成三个列表然后递归排序左右两部分。它更容易读懂但它创建了额外列表整体空间占用高于原地版本。LeetCode 等刷题场景用它解题没问题但工程中需要原地排序时仍要以 Java 或 C 版本为准。注意Python 版本的核心仍然是快速排序的分治思想但不要把它当作快速排序的标准内存模型。面试时如果要求原地排序和 (O(\log n)) 栈空间应写类似上方 Java 的分区版本。3.4 三个版本的写法差异对照实现版本排序方式主要优点需要注意的问题Java原地递归分区代码结构清晰适合学习递归方法需注意栈空间C原地递归分区性能直观贴近底层边界和下标参数容易写错Python新列表拼接最容易理解分治思想空间占用高非原地排序如果是为了快速复习原理建议先跑 Python 版本。如果是为了工程落地建议用 Java 或 C 的原地递归版本。4. 运行验证不能只看“排完序”这个结果写完代码后需要验证的不只是一组有序输出还要覆盖重复元素、负数、空数组、单元素数组等边界情况。4.1 预期输出和实际输出对照用 Java 示例运行示例数组正确输出应该如下排序前: 5 1 9 3 6 2 7 4 排序后: 1 2 3 4 5 6 7 9C 语言版本输出相同。4.2 建议至少运行下面几组测试算法验证要检查四类数据测试数据想验证什么{5, 1, 9, 3, 6, 2, 7, 4}普通乱序数据是否正常{1, 1, 1, 1}大量重复元素是否死循环{10, 9, 8, 7}完全逆序数据是否退化{3, -1, 0, 5, -8}包含负数和零的结果是否正确例如全相等数组[1, 1, 1, 1]用 Lomuto 分区时array[j] pivot返回 false所有相同值都不交换最后把基准换到i 1相当于每次只排除一个元素。这种情况不会死循环但性能退化为最坏情况。真正危险的是双指针 Hoare 分区里没有处理相等值可能导致无限交换。4.3 验证过程中还要检查递归是否正常收敛不要只依赖运行结果。可以在快速排序入口处打印每个子问题的边界观察子数组长度是否不断缩小quickSort: left0, right7 quickSort: left0, right2 quickSort: left0, right0 quickSort: left2, right2 quickSort: left4, right7 ...如果看到某个递归调用反复出现相同的left和right基本可以断定递归区间没有排除基准位置或者基准下标计算有误。5. 复杂度、稳定性和基准选择问题快速排序在各种情况下表现差异很大。要理解它为什么有时快、有时慢不能只看平均复杂度。5.1 理想递归树和平均情况理想情况下每次分区都把数组分成接近相等的两半递归深度接近 (\log_2 n)每一层的总时间复杂度是 (O(n))整体平均时间复杂度为 (O(n \log n))。这是快速排序正常工作的前提。但基准选择不好时例如每次选到最小值或最大值数组中其他元素都跑到基准同一侧递归深度变成 (n)时间复杂度就退化成 (O(n^2))。不同情况汇总如下情况时间复杂度空间复杂度典型场景平均情况(O(n \log n))(O(\log n))随机数据最好情况(O(n \log n))(O(\log n))每次分区都接近对半最坏情况(O(n^2))(O(n))有序数据配合固定端点基准稳定性不稳定需要稳定排序时应改用归并排序5.2 固定基准的问题如果固定选择最右侧元素作为基准而输入恰好是完全有序数组每趟分区只能排除最右侧的最大值左侧数组仍保留剩余所有元素递归过程退化成类似冒泡排序的形态比较次数约为 (\frac{n(n-1)}{2})。这种问题不是算法本身错误而是实现时没有考虑输入分布。工程实现中通常会通过以下方式改进基准选择策略基本思路主要优点实际场景随机基准从left到right随机选一个下标并与端点交换避免固定输入导致退化算法竞赛、排序库三数取中比较左端、中间、右端三个值取中间值作为基准兼顾有序和随机数据标准库常用双基准选择两个基准把区间分为三段减少比较次数适合大数组JDK 基本类型排序相关实现三数取中是工程中较稳妥的方案因为它实现简单且能有效避免每次选到最大或最小值。随机基准同样有效但随机数生成本身有额外开销需要权衡。5.3 空间复杂度为什么比堆排序和归并排序更值得讨论快速排序的原地交换并不需要额外数组但递归本身会消耗函数调用栈。平均递归深度约 (\log_2 n)所以空间开销约 (O(\log n))。最坏情况下递归深度达到 (n)空间开销也会退化为 (O(n))。如果排序的数据量很大例如百万级数组且输入有序固定最右基准递归深度会很大Java 默认栈空间可能在排序未完成前就抛StackOverflowError。6. 常见错误与排查路径快速排序出错时错误并不神秘。大多数问题集中在下标、递归边界和相等值处理上。6.1 递归区间没有排除基准位置quickSort(array, left, pivotIndex); quickSort(array, pivotIndex, right);这是错误的写法。第一次排序结束后pivotIndex上的元素已经处在最终位置它不能再次作为子问题参与排序。上面的写法会让某一次递归把同一个元素反复当作排序对象最终导致递归不断递归相同区间出现StackOverflowError。正确写法是quickSort(array, left, pivotIndex - 1); quickSort(array, pivotIndex 1, right);类似地中止条件必须是left right只写left right会在部分场景下标错位时漏掉空数组情况。6.2 有序数组出现超时或栈溢出现象是排序普通随机数组正常遇到已经有序的大数组时运行时间突然变长甚至栈溢出。原因通常是把基准固定在最左或最右。对于有序输入每趟分区只能排除一个元素递归树退化成一条链。排查方式是在quickSort入口打印left和right。如果发现每次递归右侧区间几乎不变或变化极小说明基准选择失败。改进方法int middle left (right - left) / 2; int pivot array[middle];这种把中间值作为基准的策略能极大缓解有序输入下的退化问题。更稳妥的是使用三数取中或随机下标。6.3 大量重复元素时出现交换错乱如果分区条件写成或时有误判可能出现在含有大量相等元素的数组上排序结果不正确。Lomuto 分区本身能处理相等值但相等值越多一次分区排除的元素越少效率越低。若要彻底优化重复元素可以引入三向切分快速排序。三向切分的思想是额外划分出“等于基准”的中间区段递归时只排序左边的小于区和右边的大于区。重复元素很多时这种方式效率提升明显。6.4 排查路径建议按照下面的顺序排查快速排序问题步骤检查内容1检查left和right初始值是否正确是否出现了right小于 02检查分区返回的下标是否是基准的真实位置3检查递归调用是否排除了pivotIndex4检查递归结束条件是否覆盖空数组和单元素数组5用全相等、逆序、有序三组测试数据验证是否有超时或死循环6如果存在超大数组查看是否属于递归深度过大7检查是否使用了额外数组以及空间复杂度是否符合预期注意快速排序里最难定位的通常不是语法错误而是“运行结果偶尔正确、偶尔错误”。这类问题大概率是分区扫描时没有正确维护指针建议在每次交换后打印当前数组。7. 工程实践和扩展方向如果只是应付考试理解递归版快速排序就够了。如果要把快速排序放进生产代码还需要考虑栈空间、基准策略、递归深度和与标准库的选型关系。7.1 生产环境可以采用的稳定改进版本工程中的快速排序通常会做以下组合优化子数组较小时改用插入排序减少递归调用次数。基准选择采用三数取中或随机策略避免最坏输入。使用显式栈代替递归或限制递归深度避免极端情况下栈溢出。数据量很大或包含大量重复元素时使用三向切分。比如在递归函数开头加一个阈值判断private static final int INSERTION_SORT_THRESHOLD 16; if (right - left 1 INSERTION_SORT_THRESHOLD) { insertionSort(array, left, right); return; }当待排序子数组长度小于 16 时直接使用插入排序。插入排序对少量元素性能好也可以减少递归层次。这是很多排序库常用的边界处理思路。7.2 迭代版快速排序的思路递归版快速排序在极端情况可能因为栈空间不足而失败。如果希望避免递归可以使用显式栈保存待排序区间。public static void quickSortIterative(int[] array) { if (array.length 1) { return; } Dequeint[] stack new ArrayDeque(); stack.push(new int[]{0, array.length - 1}); while (!stack.isEmpty()) { int[] range stack.pop(); int left range[0]; int right range[1]; if (left right) { continue; } int pivotIndex partition(array, left, right); if (pivotIndex - 1 left) { stack.push(new int[]{left, pivotIndex - 1}); } if (pivotIndex 1 right) { stack.push(new int[]{pivotIndex 1, right}); } } }显式栈需要自己控制区间入栈顺序。这里两个子区间是否入栈都先判断长度大于 1避免把空区间或单元素区间重复压入。7.3 标准库里的相关应用很多语言的内置排序并没有停留在最原始的快速排序版本。Java 的Arrays.sort对基本类型数组的排序实现采用过多基准快速排序相关思路归并排序则更适合对象数组排序因为需要保证稳定性。C 标准库的qsort原型为快速排序形式但不同编译器的实际排序实现也会有各自优化。使用标准库排序比自己手写排序更可靠因为标准库针对大规模数据做了专项优化。手写快速排序主要适合教学、算法面试、自定义排序逻辑以及对排序过程有特殊性能要求且能确认输入特征的场景。工程原则不要因为“快速排序速度快”就一律手写。先确认排序稳定性、数据规模、是否需要原地排序、是否存在大量有序或重复数据。多数情况下直接使用语言内置排序即可。7.4 给学习者的练习顺序建议快速排序是值得反复手写的基础算法。建议按下面顺序完成练习使用 Lomuto 分区写一个固定最右基准的递归版本并通过普通数组测试。改用固定中间值作为基准重新跑有序和逆序测试。实现三数取中分区版。实现 Hoare 版双指针递归版本对比代码差异。把递归改成显式栈迭代版本。在子数组很短时引入插入排序观察不同数据规模上的性能表现。实现三向切分快速排序用大量重复元素测试。每一步之间都保留可运行代码和测试输出。不要一次写完多版本再调试否则出问题时很难定位是分区逻辑、递归边界还是基准策略导致。快速排序的难点不在于“分治”这个宏观概念而在于细节执行。基准归位后不能被再次递归左右指针的移动必须符合分区目标递归结束时必须覆盖空区间随机或重复数据的性能表现取决于基准策略。把这几个点真正想清楚后快速排序就能从“会背的模板”变成“能按需改写的工具”。后续如果再深入归并排序、堆排序、三向切分以及各种外部排序会发现它们都以类似的方式处理边界条件快速排序是最好的起步训练场。
快速排序详解：分治、基准选择与工程优化实践
快速排序Quick Sort是排序算法中概念清晰、实现却很考验细节的一类算法。它常常被用于教学演示也因为平均时间复杂度为 (O(n \log n))、额外空间占用小成为很多标准库排序实现的重要基础。可不少学习者背下代码后一旦换一种基准选择方式或者换一组含大量重复元素的数组程序就会出现排序错误甚至栈溢出。要真正掌握快速排序最有效的办法不是死记递归代码而是先把“分区Partition”过程在脑中完整推演一遍再去看代码每一步对应的动作。这篇文章会用适合动画讲解的方式拆解快速排序先讲清楚分治和基准之间的关系再用一个具体数组逐步演示指针移动、交换和递归调用过程最后给出 Java、C 和 Python 的参考实现并补充常见错误排查、性能分析和工程优化建议。如果你正在准备算法面试或者想亲手实现一个能放进项目里的排序工具这篇文章可以当作从理解到落地的完整笔记。1. 快速排序真正在解决什么分治思想下的基准归位快速排序的核心不是“把整个数组一次排好”而是每次只解决一个元素的最终位置问题。选中数组中的某个值作为基准pivot经过一趟分区后所有小于基准的值都放到基准左边所有大于基准的值都放到基准右边。此时基准已经处于整个数组排序后的正确位置它不需要再参与后续移动。这个过程要反复递归执行。左边的子数组做一次快速排序右边的子数组再做一次快速排序直到每个子数组的长度为 0 或 1。整体思路来自分治法把大问题拆成两个规模更小、互相独立的小问题。1.1 分区操作是整个算法的心脏排序是否正确代码是否能终止基本都被分区这一步决定。常见的分区方式有两种一种是 Lomuto 分区使用单向指针从左向右扫描逻辑直观适合教学和入门实现。另一种是 Hoare 分区使用左右两个指针向中间靠近交换次数通常更少效率更高但边界条件更难写对。两种分区的共同目标只有一个经过一轮数组遍历后返回基准元素的下标并确保基准左侧不大于基准、右侧不小于基准。1.2 稳定性和原地排序要先分清排序算法有两个常用判断标准是否稳定是否原地排序。稳定指的是排序前后相等元素的相对顺序不被改变。快速排序分区时会交换相隔较远的元素因此不是稳定排序。原地排序指的是排序过程中不需要申请额外的大块内存主要借助原数组交换元素完成。快速排序通常是原地排序但递归调用会消耗函数调用栈空间这一点在生产环境里值得注意。对于双关键字排序等需要保留原始先后顺序的场景例如先按时间再按优先级排序快速排序不能直接依赖应使用归并排序等稳定排序算法。2. 把快速排序当动画看一次完整的分区推演动画或者图示之所以能帮助理解是因为排序本质上就是一系列状态变化。我们需要观察的变量只有几个当前子数组的范围、基准的值、扫描指针的位置以及发生交换的时刻。下面以数组作为示例[5, 1, 9, 3, 6, 2, 7, 4]采用 Lomuto 分区暂时固定选择最右侧元素作为基准。选择最右侧元素是为了代码简单教学演示时最容易跟踪但它不是工程上最好的选择后文会单独分析。2.1 先定义两个指针的含义Lomuto 分区需要两个变量i最后一个“已经确认小于基准”的元素所在下标初始为left - 1。j当前扫描指针从left向right - 1移动。每次当array[j] pivot时先把i向后移动一位再交换array[i]和array[j]。这样做的效果是把小于基准的值不断往数组左侧堆放。一趟扫描结束后所有小于基准的值都集中在i及其左侧。把基准和array[i 1]交换基准就回到了最终位置分区结束。2.2 逐轮观察指针和数组变化对于数组[5, 1, 9, 3, 6, 2, 7, 4]最右侧基准是4。初始i -1 j 0扫描 5 5 4 不成立不交换j 1扫描 1 1 4 成立 i 变为 0 交换 array[0] 和 array[1] 数组变为[1, 5, 9, 3, 6, 2, 7, 4]j继续向后扫描j 2扫描 9 9 4 不成立 j 3扫描 3 3 4 成立 i 变为 1 交换 array[1] 和 array[3] 数组变为[1, 3, 9, 5, 6, 2, 7, 4]继续扫描j 4扫描 6 6 4 不成立 j 5扫描 2 2 4 成立 i 变为 2 交换 array[2] 和 array[5] 数组变为[1, 3, 2, 5, 6, 9, 7, 4]j 6扫描 7 7 4 不成立 扫描结束此时i 2array[i 1] array[3] 5。把基准4与5交换得到[1, 3, 2, 4, 6, 9, 7, 5]返回基准下标3。从这一刻开始数字4已经处在最终正确位置左边的[1, 3, 2]都小于 4右边的[6, 9, 7, 5]都大于 4。2.3 观察动画时要抓住哪些关键点看快速排序动画时不建议只关注最后的排序结果而是按以下顺序观察当前这一段子数组的left和right边界在哪里。选中的基准原先是哪个位置的值。扫描过程中发生了哪几次交换。分区结束后基准落在哪个下标。递归进入哪两个子问题顺序是什么。动画的价值在于把“数组下标变化”变成可视状态。如果只看代码容易忽略递归区间为何不能包含刚刚返回的基准。看动画时容易明白基准已经归位左右两侧互相独立不能再把基准放入任何一侧的递归范围。2.4 第一轮结束后递归如何继续第一轮分区的结果是下标3上的4已经归位。接下来快速排序分别处理左子数组[1, 3, 2] 右子数组[6, 9, 7, 5]左子数组递归时边界是原数组下标0到2右子数组递归时边界是原数组下标4到7。如果代码写成把4再次包含进某一边结果不会立刻报错但会导致递归无法收敛最终出现栈溢出。这是快速排序初学阶段最典型的问题之一。3. 从推演到代码Java 和 C 的参考实现动画推演已经明确了分区的动作。写成代码时关键是保证变量含义和推演时保持一致。3.1 Java 实现从分区函数开始写先写分区函数。这里固定选择最右侧元素作为基准是为了让代码和上面推演完全对应。public class QuickSortDemo { public static void quickSort(int[] array, int left, int right) { if (left right) { return; } int pivotIndex partition(array, left, right); quickSort(array, left, pivotIndex - 1); quickSort(array, pivotIndex 1, right); } private static int partition(int[] array, int left, int right) { int pivot array[right]; int i left - 1; for (int j left; j right; j) { if (array[j] pivot) { i; swap(array, i, j); } } swap(array, i 1, right); return i 1; } private static void swap(int[] array, int indexA, int indexB) { int temp array[indexA]; array[indexA] array[indexB]; array[indexB] temp; } public static void main(String[] args) { int[] sample {5, 1, 9, 3, 6, 2, 7, 4}; System.out.print(排序前: ); printArray(sample); quickSort(sample, 0, sample.length - 1); System.out.print(排序后: ); printArray(sample); } private static void printArray(int[] array) { for (int value : array) { System.out.print(value ); } System.out.println(); } }这段代码的关键点在quickSort的递归边界。partition返回pivotIndex后左侧递归范围是left到pivotIndex - 1右侧递归范围是pivotIndex 1到right。基准位置本身不再进入递归。3.2 C 语言实现保持相同逻辑C 语言版本和 Java 版本几乎完全一致只是数组传入方式不同。完整代码如下#include stdio.h void swap(int array[], int indexA, int indexB) { int temp array[indexA]; array[indexA] array[indexB]; array[indexB] temp; } int partition(int array[], int left, int right) { int pivot array[right]; int i left - 1; for (int j left; j right; j) { if (array[j] pivot) { i; swap(array, i, j); } } swap(array, i 1, right); return i 1; } void quickSort(int array[], int left, int right) { if (left right) { return; } int pivotIndex partition(array, left, right); quickSort(array, left, pivotIndex - 1); quickSort(array, pivotIndex 1, right); } void printArray(int array[], int size) { for (int i 0; i size; i) { printf(%d , array[i]); } printf(\n); } int main() { int sample[] {5, 1, 9, 3, 6, 2, 7, 4}; int size sizeof(sample) / sizeof(sample[0]); printf(排序前: ); printArray(sample, size); quickSort(sample, 0, size - 1); printf(排序后: ); printArray(sample, size); return 0; }在 C 语言环境中要注意原数组通过引用传递递归函数里的交换直接作用在原数组上不需要额外返回数组。如果从partition返回的是数组而不是下标说明概念上还没完全切换过来。3.3 Python 简洁写法便于理解但和原地版本不同Python 也可以写出非常适合表达的版本。下面的写法返回新数组不对原数组原地修改教学方便但生产使用时要注意它会产生多个新列表def quick_sort(nums): if len(nums) 1: return nums pivot nums[len(nums) // 2] left [x for x in nums if x pivot] middle [x for x in nums if x pivot] right [x for x in nums if x pivot] return quick_sort(left) middle quick_sort(right) sample [5, 1, 9, 3, 6, 2, 7, 4] print(排序前:, sample) print(排序后:, quick_sort(sample))这个版本把小于、等于、大于基准的元素拆成三个列表然后递归排序左右两部分。它更容易读懂但它创建了额外列表整体空间占用高于原地版本。LeetCode 等刷题场景用它解题没问题但工程中需要原地排序时仍要以 Java 或 C 版本为准。注意Python 版本的核心仍然是快速排序的分治思想但不要把它当作快速排序的标准内存模型。面试时如果要求原地排序和 (O(\log n)) 栈空间应写类似上方 Java 的分区版本。3.4 三个版本的写法差异对照实现版本排序方式主要优点需要注意的问题Java原地递归分区代码结构清晰适合学习递归方法需注意栈空间C原地递归分区性能直观贴近底层边界和下标参数容易写错Python新列表拼接最容易理解分治思想空间占用高非原地排序如果是为了快速复习原理建议先跑 Python 版本。如果是为了工程落地建议用 Java 或 C 的原地递归版本。4. 运行验证不能只看“排完序”这个结果写完代码后需要验证的不只是一组有序输出还要覆盖重复元素、负数、空数组、单元素数组等边界情况。4.1 预期输出和实际输出对照用 Java 示例运行示例数组正确输出应该如下排序前: 5 1 9 3 6 2 7 4 排序后: 1 2 3 4 5 6 7 9C 语言版本输出相同。4.2 建议至少运行下面几组测试算法验证要检查四类数据测试数据想验证什么{5, 1, 9, 3, 6, 2, 7, 4}普通乱序数据是否正常{1, 1, 1, 1}大量重复元素是否死循环{10, 9, 8, 7}完全逆序数据是否退化{3, -1, 0, 5, -8}包含负数和零的结果是否正确例如全相等数组[1, 1, 1, 1]用 Lomuto 分区时array[j] pivot返回 false所有相同值都不交换最后把基准换到i 1相当于每次只排除一个元素。这种情况不会死循环但性能退化为最坏情况。真正危险的是双指针 Hoare 分区里没有处理相等值可能导致无限交换。4.3 验证过程中还要检查递归是否正常收敛不要只依赖运行结果。可以在快速排序入口处打印每个子问题的边界观察子数组长度是否不断缩小quickSort: left0, right7 quickSort: left0, right2 quickSort: left0, right0 quickSort: left2, right2 quickSort: left4, right7 ...如果看到某个递归调用反复出现相同的left和right基本可以断定递归区间没有排除基准位置或者基准下标计算有误。5. 复杂度、稳定性和基准选择问题快速排序在各种情况下表现差异很大。要理解它为什么有时快、有时慢不能只看平均复杂度。5.1 理想递归树和平均情况理想情况下每次分区都把数组分成接近相等的两半递归深度接近 (\log_2 n)每一层的总时间复杂度是 (O(n))整体平均时间复杂度为 (O(n \log n))。这是快速排序正常工作的前提。但基准选择不好时例如每次选到最小值或最大值数组中其他元素都跑到基准同一侧递归深度变成 (n)时间复杂度就退化成 (O(n^2))。不同情况汇总如下情况时间复杂度空间复杂度典型场景平均情况(O(n \log n))(O(\log n))随机数据最好情况(O(n \log n))(O(\log n))每次分区都接近对半最坏情况(O(n^2))(O(n))有序数据配合固定端点基准稳定性不稳定需要稳定排序时应改用归并排序5.2 固定基准的问题如果固定选择最右侧元素作为基准而输入恰好是完全有序数组每趟分区只能排除最右侧的最大值左侧数组仍保留剩余所有元素递归过程退化成类似冒泡排序的形态比较次数约为 (\frac{n(n-1)}{2})。这种问题不是算法本身错误而是实现时没有考虑输入分布。工程实现中通常会通过以下方式改进基准选择策略基本思路主要优点实际场景随机基准从left到right随机选一个下标并与端点交换避免固定输入导致退化算法竞赛、排序库三数取中比较左端、中间、右端三个值取中间值作为基准兼顾有序和随机数据标准库常用双基准选择两个基准把区间分为三段减少比较次数适合大数组JDK 基本类型排序相关实现三数取中是工程中较稳妥的方案因为它实现简单且能有效避免每次选到最大或最小值。随机基准同样有效但随机数生成本身有额外开销需要权衡。5.3 空间复杂度为什么比堆排序和归并排序更值得讨论快速排序的原地交换并不需要额外数组但递归本身会消耗函数调用栈。平均递归深度约 (\log_2 n)所以空间开销约 (O(\log n))。最坏情况下递归深度达到 (n)空间开销也会退化为 (O(n))。如果排序的数据量很大例如百万级数组且输入有序固定最右基准递归深度会很大Java 默认栈空间可能在排序未完成前就抛StackOverflowError。6. 常见错误与排查路径快速排序出错时错误并不神秘。大多数问题集中在下标、递归边界和相等值处理上。6.1 递归区间没有排除基准位置quickSort(array, left, pivotIndex); quickSort(array, pivotIndex, right);这是错误的写法。第一次排序结束后pivotIndex上的元素已经处在最终位置它不能再次作为子问题参与排序。上面的写法会让某一次递归把同一个元素反复当作排序对象最终导致递归不断递归相同区间出现StackOverflowError。正确写法是quickSort(array, left, pivotIndex - 1); quickSort(array, pivotIndex 1, right);类似地中止条件必须是left right只写left right会在部分场景下标错位时漏掉空数组情况。6.2 有序数组出现超时或栈溢出现象是排序普通随机数组正常遇到已经有序的大数组时运行时间突然变长甚至栈溢出。原因通常是把基准固定在最左或最右。对于有序输入每趟分区只能排除一个元素递归树退化成一条链。排查方式是在quickSort入口打印left和right。如果发现每次递归右侧区间几乎不变或变化极小说明基准选择失败。改进方法int middle left (right - left) / 2; int pivot array[middle];这种把中间值作为基准的策略能极大缓解有序输入下的退化问题。更稳妥的是使用三数取中或随机下标。6.3 大量重复元素时出现交换错乱如果分区条件写成或时有误判可能出现在含有大量相等元素的数组上排序结果不正确。Lomuto 分区本身能处理相等值但相等值越多一次分区排除的元素越少效率越低。若要彻底优化重复元素可以引入三向切分快速排序。三向切分的思想是额外划分出“等于基准”的中间区段递归时只排序左边的小于区和右边的大于区。重复元素很多时这种方式效率提升明显。6.4 排查路径建议按照下面的顺序排查快速排序问题步骤检查内容1检查left和right初始值是否正确是否出现了right小于 02检查分区返回的下标是否是基准的真实位置3检查递归调用是否排除了pivotIndex4检查递归结束条件是否覆盖空数组和单元素数组5用全相等、逆序、有序三组测试数据验证是否有超时或死循环6如果存在超大数组查看是否属于递归深度过大7检查是否使用了额外数组以及空间复杂度是否符合预期注意快速排序里最难定位的通常不是语法错误而是“运行结果偶尔正确、偶尔错误”。这类问题大概率是分区扫描时没有正确维护指针建议在每次交换后打印当前数组。7. 工程实践和扩展方向如果只是应付考试理解递归版快速排序就够了。如果要把快速排序放进生产代码还需要考虑栈空间、基准策略、递归深度和与标准库的选型关系。7.1 生产环境可以采用的稳定改进版本工程中的快速排序通常会做以下组合优化子数组较小时改用插入排序减少递归调用次数。基准选择采用三数取中或随机策略避免最坏输入。使用显式栈代替递归或限制递归深度避免极端情况下栈溢出。数据量很大或包含大量重复元素时使用三向切分。比如在递归函数开头加一个阈值判断private static final int INSERTION_SORT_THRESHOLD 16; if (right - left 1 INSERTION_SORT_THRESHOLD) { insertionSort(array, left, right); return; }当待排序子数组长度小于 16 时直接使用插入排序。插入排序对少量元素性能好也可以减少递归层次。这是很多排序库常用的边界处理思路。7.2 迭代版快速排序的思路递归版快速排序在极端情况可能因为栈空间不足而失败。如果希望避免递归可以使用显式栈保存待排序区间。public static void quickSortIterative(int[] array) { if (array.length 1) { return; } Dequeint[] stack new ArrayDeque(); stack.push(new int[]{0, array.length - 1}); while (!stack.isEmpty()) { int[] range stack.pop(); int left range[0]; int right range[1]; if (left right) { continue; } int pivotIndex partition(array, left, right); if (pivotIndex - 1 left) { stack.push(new int[]{left, pivotIndex - 1}); } if (pivotIndex 1 right) { stack.push(new int[]{pivotIndex 1, right}); } } }显式栈需要自己控制区间入栈顺序。这里两个子区间是否入栈都先判断长度大于 1避免把空区间或单元素区间重复压入。7.3 标准库里的相关应用很多语言的内置排序并没有停留在最原始的快速排序版本。Java 的Arrays.sort对基本类型数组的排序实现采用过多基准快速排序相关思路归并排序则更适合对象数组排序因为需要保证稳定性。C 标准库的qsort原型为快速排序形式但不同编译器的实际排序实现也会有各自优化。使用标准库排序比自己手写排序更可靠因为标准库针对大规模数据做了专项优化。手写快速排序主要适合教学、算法面试、自定义排序逻辑以及对排序过程有特殊性能要求且能确认输入特征的场景。工程原则不要因为“快速排序速度快”就一律手写。先确认排序稳定性、数据规模、是否需要原地排序、是否存在大量有序或重复数据。多数情况下直接使用语言内置排序即可。7.4 给学习者的练习顺序建议快速排序是值得反复手写的基础算法。建议按下面顺序完成练习使用 Lomuto 分区写一个固定最右基准的递归版本并通过普通数组测试。改用固定中间值作为基准重新跑有序和逆序测试。实现三数取中分区版。实现 Hoare 版双指针递归版本对比代码差异。把递归改成显式栈迭代版本。在子数组很短时引入插入排序观察不同数据规模上的性能表现。实现三向切分快速排序用大量重复元素测试。每一步之间都保留可运行代码和测试输出。不要一次写完多版本再调试否则出问题时很难定位是分区逻辑、递归边界还是基准策略导致。快速排序的难点不在于“分治”这个宏观概念而在于细节执行。基准归位后不能被再次递归左右指针的移动必须符合分区目标递归结束时必须覆盖空区间随机或重复数据的性能表现取决于基准策略。把这几个点真正想清楚后快速排序就能从“会背的模板”变成“能按需改写的工具”。后续如果再深入归并排序、堆排序、三向切分以及各种外部排序会发现它们都以类似的方式处理边界条件快速排序是最好的起步训练场。