提到排序算法快速排序基本是笔试、面试和工程实战里出场率最高的一个。很多朋友第一次看代码时感觉逻辑还能懂但一旦问到“为什么这样交换”“基准元素到底怎么放回去”“递归之后数组为什么就对了”就容易卡住。为了讲清楚本文用“动画思路”来拆解快速排序把每一次指针移动、每一轮交换都当作画面来呈现同时给出 C 语言和 Java 的完整可运行代码帮助你从原理到实现一次打通。如果你准备算法面试或者想彻底告别“背代码但画不出过程”的状态这篇文章很适合你。读完你会掌握快速排序的完整流程、分区函数的不同写法、时间复杂度的推导以及有序数组下性能退化的原因和优化手段。1. 为什么快速排序值得反复看1.1 快速排序解决什么问题排序是编程里最基础的需求之一给定一组无序数据按照从小到大或从大到小排列。快速排序是目前使用最广泛的排序算法之一很多编程语言内置排序函数的底层都包含快速排序的思想。打个比方如果排序是一所学校要给全校学生按照身高排队冒泡排序的做法是相邻两个人不断比较、交换像气泡一样把高个子慢慢推到后面。快速排序的做法则更像“分组管理”先找出一个参考身高的人让比他矮的都站到左边比他高的都站到右边。这样一来这个参考人已经站在了最终位置左侧和右侧的人只需要在各自小组里继续重复同样的动作即可。在真实工程中快速排序之所以受欢迎是因为它在多数情况下能做到 O(n log n) 的平均时间复杂度而且排序过程是在原数组内部完成不需要额外的大块内存属于原地排序。1.2 一对关键概念递归与分治快速排序的实现离不开两个重要的算法思想分治Divide and Conquer和递归Recursion。所谓分治就是把一个大规模问题拆分若干个规模更小、结构相似的子问题分别解决后再合并结果。快速排序把数组拆成左半部分所有元素都小于等于基准。一个基准元素它已经在正确的最终位置。右半部分所有元素都大于等于基准。由于左右两部分继续使用同样的排序逻辑就非常适合用递归来实现。每次递归调用做同一件事把当前区间内的数据分成左右两块让基准元素归位。这里有一个初学者容易绕晕的点快速排序不是“先整体排好再递归处理左右”而是“每轮只保证基准元素的位置左右两侧还乱着靠递归一点点把乱的部分也理清”。这种动态过程用文字描述不如“画面感”直观所以接下来我们用多个详细步骤来拆解。2. 快速排序整体流程拆解2.1 三步循环快速排序的主流程可以用三步来概括选择一个基准值pivot。对当前区间做分区partition把小于基准的值放到左边大于基准的值放到右边并把基准放到它最终的位置。对基准左边和右边的子区间递归执行同样的步骤。其中第 2 步是快速排序的核心。做完一次分区后数组并不会立刻有序但基准元素不会再去动它因为它的位置已经正确。左右两侧继续递归不断缩小范围直到每个子区间只剩一个元素或者为空整个数组就自然有序了。递归仍然不好理解的同学可以把“只剩下一个元素”看作递归出口。一个元素本身已经有序不需要再排序此时函数直接返回不再向下递归。2.2 动画视角看一轮完整分区为了看清动态过程我们拿一个实际数组来演示。假设现在要对下面这个数组从小到大排序[5, 3, 8, 4, 2, 7, 1, 6]我们选择第一个元素 5 作为基准值 pivot。目标是把小于 5 的放到左边大于 5 的放到右边并且让 5 落到正确位置。我采用“挖坑填数”的方式演示这也是最容易”脑补“成动画的一种分区方式第一步把基准值 5 从数组里取出来相当于位置 0 留下一个“坑”坑, 3, 8, 4, 2, 7, 1, 6从右往左找小于 5 的数。右边第一个数是 6不满足继续往左遇到 1满足条件。把 1 填到左边的坑里1, 3, 8, 4, 2, 7, 坑, 6此时右边原来放 1 的位置变成了新的坑。接下来从左往右找大于 5 的数。左边已经是 1、3都不大于 5继续向右遇到 8满足条件。把 8 填到右边的坑里1, 3, 坑, 4, 2, 7, 8, 6此时左边原来放 8 的位置又变成坑。继续从右往左找小于 5 的数。当前右边是 7不满足继续向左遇到 2满足条件。把 2 填到左边的坑1, 3, 2, 4, 坑, 7, 8, 6接着从左往右找大于 5 的数。4 不大于 5继续往右左右指针相遇在位置 4。此时把基准值 5 填进这个坑1, 3, 2, 4, 5, 7, 8, 6这一轮结束后5 左边都是小于它的数5 右边都是大于它的数。5 所在的下标是 4它已经位于最终位置不需要再移动。之后只需要对左边区间[1, 3, 2, 4]和右边区间[7, 8, 6]分别递归执行相同操作。把上面过程在脑中“动”起来你会发现整个过程就像左右两个指针在交替寻找可以填坑的元素这也是“动画讲解快速排序”时最核心的画面。2.3 递归出口很关键递归函数必须有出口否则会无限调用直到栈溢出。快速排序的递归出口是区间左边界大于等于右边界说明当前区间元素个数为 0 或 1无需排序。例如处理[7, 8, 6]时再次分区后得到[6]和[8]两个子区间都只有一个元素下一轮递归直接返回。算法不再继续切分最终整个数组完成排序。3. 基准元素的选择影响效率3.1 固定选第一个或最后一个元素最简单的基准选择策略是固定取当前区间的第一个元素或最后一个元素。代码写起来方便但存在明显缺点如果数组本身接近有序每次选到的基准很可能正好是当前区间的最小值或最大值分区结果会非常不平衡导致快速排序退化为 O(n²)。举一个例子数组已经是[1, 2, 3, 4, 5]固定选第一个元素 1 作为基准。分区后左边为空右边是[2, 3, 4, 5]每次只能减少一个元素递归深度变成 n总比较次数接近 n (n-1) ... 1也就是 O(n²)。所以固定选基准虽然代码最简但在生产级实现里并不推荐。3.2 随机选基准改进思路之一是随机选一个下标作为基准。随机化之后数组有序时不再每次都选中最小或最大值出现最坏情况的概率大幅降低。实现时需要注意选随机下标后可以把这个下标的值和区间第一个元素交换这样后续分区逻辑仍然按照原来的模板走不需要额外修改。3.3 三数取中法工程中最常用的折中方案是“三数取中”Median of Three从区间左端、中间、右端取出三个元素选择数值居中的那个作为基准。例如区间是[left, mid, right]分别对应9, 1, 5那么基准应该取中间的 5。这个方案既避免了纯随机带来的不确定性又能在有序数组上得到比较好的分区效果。JDK 的排序实现、很多标准库内部都会考虑类似的策略。对普通学习来说直接用第一个元素作为基准即可因为重点在于理解算法过程但在实际产品代码里最好至少加上随机化或三数取中。4. 分区函数快速排序的灵魂4.1 分区负责什么分区函数要做的事是在一个数组中选定一个基准然后通过比较和交换把数组整理成“左小右大”的结构最后返回基准元素的下标。这个返回值非常重要。主排序函数拿到基准下标之后就可以确定下一次递归的范围左子区间[left, pivotIndex - 1]右子区间[pivotIndex 1, right]很多初学快速排序的同学会写错原因往往不是整体框架而是分区函数里指针移动和交换的顺序写错。4.2 两种常见的分区思路业界有几类分区写法这里介绍最主流的两种。第一种是“挖坑法”。前面演示用到的就是这种方法。实现时先保存基准值相当于把基准位置挖成一个坑然后右指针向左找小于基准的值来填左边的坑左指针向右找大于基准的值来填右边的坑直到两个指针相遇最后把基准值放进相遇位置。第二种是“Lomuto 分区法”。这是很多算法教材里常见的写法代码更短。它通常选最后一个元素作为基准用两个指针 i 和 j 同时从左往右扫描j 负责遍历每个元素。i 负责指向“小于等于基准的区域”的末尾。当 j 遇到小于等于基准的元素时把 i 后移一位并交换 i 与 j 位置的值。遍历结束后将基准与 i1 位置的值交换。无论使用哪种分区写法关键点都是分区完成后基准前面的元素都满足小于等于基准基准后面的元素都满足大于等于基准。4.3 看动画时重点看的三个细节很多快速排序动画里不同颜色的小方块代表不同元素两根指针或两个下标在不断移动。想从动画里真正学到东西建议重点看三个细节第一坑的位置如何从左跳到右、又从右跳回左。这是理解挖坑法的钥匙。第二为什么两个指针最终会相遇。因为每次填坑后区间会不断向中间收缩坑的位置也在变化最终左右指针落在同一个位置这个位置就是基准的归宿。第三递归结束后数组如何逐渐从“局部正确”变成“整体正确”。每一轮分区只保证一个基准归位但因为递归的作用所有元素都会依次归位。5. C 语言实现快速排序5.1 使用挖坑法的 C 代码先来一段常见且易于理解的 C 语言实现。这个版本使用第一个元素作为基准采用挖坑法分区。#include stdio.h // 分区函数对 arr[left..right] 进行分区返回基准最终下标 int partition(int arr[], int left, int right) { int pivot arr[left]; // 挖坑先把基准值保存起来 while (left right) { // 从右往左找小于基准的值 while (left right arr[right] pivot) { right--; } // 找到后填到左边的坑 arr[left] arr[right]; // 从左往右找大于基准的值 while (left right arr[left] pivot) { left; } // 找到后填到右边的坑 arr[right] arr[left]; } // left 和 right 相遇把基准值放入坑中 arr[left] pivot; return left; } // 快速排序递归函数 void quickSort(int arr[], int left, int right) { if (left right) { return; } int pivotIndex partition(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex 1, right); } // 打印数组 void printArray(int arr[], int size) { for (int i 0; i size; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {5, 3, 8, 4, 2, 7, 1, 6}; int size sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, size); quickSort(arr, 0, size - 1); printf(排序后); printArray(arr, size); return 0; }运行这段代码控制台会输出排序前5 3 8 4 2 7 1 6 排序后1 2 3 4 5 6 7 85.2 结合动画再读一遍代码看这段 C 代码的时候一定要把partition函数里的while (left right)想象成两个左右移动的指针。外层while (left right)是不断收缩区间。只要左右指针没有相遇说明还没有确定基准的位置。内部第一个while让右指针向左移动直到找到比基准小的数字内部第二个while让左指针向右移动直到找到比基准大的数字。比较常见的出错点是漏写内层循环里的left right条件。如果漏写右指针可能会越过左指针导致基准位置错误甚至访问数组越界。因此在写代码时这两个内层判断不能省。5.3 C 语言实现注意事项C 语言中数组作为函数参数时会退化为指针因此quickSort内不要试图直接计算数组长度必须在调用处把right下标传入。示例代码里用sizeof(arr) / sizeof(arr[0])计算长度也是在main函数中完成的并没有传给子函数后再次计算。6. Java 实现快速排序6.1 基础版 Java 代码Java 实现同样基于递归和分区。下面这段代码使用 Lomuto 分区法基准选择当前区间最后一个元素。相比挖坑法它的代码更紧凑也是很多算法教材采用的版本。import java.util.Arrays; public class QuickSort { // Lomuto 分区选最后一个元素作为基准 public static int partition(int[] arr, int low, int high) { int pivot arr[high]; int i low - 1; // i 指向小于等于基准的那一段的末尾 for (int j low; j high; j) { if (arr[j] pivot) { i; // 将较小的元素交换到前面 int temp arr[i]; arr[i] arr[j]; arr[j] temp; } } // 将基准放到正确位置 int temp arr[i 1]; arr[i 1] arr[high]; arr[high] temp; return i 1; } public static void quickSort(int[] arr, int low, int high) { if (low high) { int pivotIndex partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex 1, high); } } public static void main(String[] args) { int[] arr {5, 3, 8, 4, 2, 7, 1, 6}; System.out.println(排序前 Arrays.toString(arr)); quickSort(arr, 0, arr.length - 1); System.out.println(排序后 Arrays.toString(arr)); } }运行后输出排序前[5, 3, 8, 4, 2, 7, 1, 6] 排序后[1, 2, 3, 4, 5, 6, 7, 8]6.2 Lomuto 分区的过程如何用动画理解Lomuto 分区可以想象成一只手在维护“已经确认小于基准”的边界。指针 j 像扫描镜头从 low 一路滑到 high 前一个位置。每扫描到一个小于等于基准的数值它就把这个数值和“边界后面的元素”交换也就是把 i 向后移动一格。这个过程像把小于基准的小球不断捡到左边篮子里最后再把基准放到篮子的右边。当数组中有很多重复元素时建议使用而不是。这里不展开读者可以尝试把 Lomuto 实现里的改成并运行包含重复元素的数组观察结果差异这有助于理解基准的归位条件。6.3 Java 泛型与对象排序思路上面代码只处理int[]。实际项目中Java 经常需要对对象数组或集合排序。更方便的方式是依赖Comparable或Comparator。例如你可以把基准比较提取成一个方法让数组元素类型变成泛型T配合比较器决定谁在前谁在后。不过工程实现中直接使用Arrays.sort()或Collections.sort()已经足够高效没有必要为普通业务数据手写快速排序。自己实现快速排序更多用于算法学习、面试考察和特殊场景的定制优化。7. 时间复杂度、空间复杂度与稳定性7.1 时间复杂度如何推导快速排序的时间复杂度与基准选择密切相关。在理想情况下每次分区都能把数组分成两个长度大致相等的部分。每层递归对所有元素进行一次遍历单层时间是 O(n)。递归深度是 O(log n)因此总时间复杂度是 O(n log n)。在最坏情况下每次基准都是当前区间的最小值或最大值导致分区后一侧为空、另一侧有 n-1 个元素。递归深度退化为 O(n)总比较次数约为 n (n-1) ... 1因此时间复杂度退化为 O(n²)。所以快速排序的平均时间复杂度是 O(n log n)最坏时间复杂度是 O(n²)。7.2 空间复杂度快速排序的空间主要消耗在递归调用产生的栈空间上。理想情况下递归深度为 O(log n)因此空间复杂度为 O(log n)。最坏情况下递归深度为 O(n)空间复杂度也退化为 O(n)。很多人误以为快速排序是完全原地排序所以空间复杂度是 O(1)这并不准确。快速排序虽然没有大量额外数组但递归调用本身会占用调用栈不能简单看作 O(1)。7.3 稳定性为什么重要又为什么快排不满足稳定排序的定义是如果两个元素的原始顺序本就符合业务要求当它们的排序关键字相等时排序后相对顺序保持不变。在整数排序场景中稳定性看似无关紧要但在多字段排序时比如先按时间排序、再按优先级排序稳定的排序能保留前一轮的排序结果。快速排序是不稳定排序。原因是分区过程中可能会把右边小于基准的元素交换到左边而这些交换可能导致相等元素的相对位置发生变化。看一个简单例子数组为[5a, 3, 5b, 2]如果基准选择某个值后需要把靠后的5b与比它小的元素交换两个相等元素5a、5b的先后顺序就可能被改变。因此当业务明确要求稳定排序时应该选择归并排序等稳定算法。8. 快速排序的退化场景与常见优化8.1 什么情况下性能会退化最容易导致性能退化的场景是输入数组已经基本有序或完全有序同时又固定选择第一个或最后一个元素作为基准。此时每次分区只拿掉一个元素递推关系接近 T(n) T(n-1) O(n)累加得到 O(n²)。除了有序数组大量重复元素也会带来性能问题。普通分区法遇到全部元素相等时一侧可能收集全部元素另一侧为空同样会造成不必要的递归和比较。8.2 三路快速排序针对大量重复元素常见优化是“三路快速排序”3-Way QuickSort。普通快速排序把数组分成两部分小于等于基准和大于等于基准三路快速排序则分成三个区间小于基准的部分。等于基准的部分。大于基准的部分。处理完一轮后所有等于基准的元素都已经处在一个连续的中间区间里不需要再参与后续递归。这样遇到大量重复元素时递归处理的区间大幅缩小性能有明显提升。Java 的Arrays.sort()对基本类型数组使用双基准快速排序Dual-Pivot QuickSort它把数组分成三段区间思想与三路快排有相通之处都能尽量避免重复元素带来的性能下降。8.3 工程实现中的混合策略真实的标准库里很少只依赖基本快速排序来解决所有情况。常见的混合策略包括递归区间较小时改用插入排序因为小数组上插入排序的常数开销更小。递归深度超过一定阈值时改用堆排序防止有序输入导致 O(n²)。基准选择使用三数取中或随机化。这种“检测到递归退化就换算法”的思路被称为 Introsort。C 标准库的std::sort就综合使用了快排、插入排序和堆排序的思想。对读者来说理解这些优化不是为了记住复杂代码而是为了遇到性能问题时知道从哪里入手分析。9. 快速排序常见错误与排查思路9.1 高频错误现象与解决方案问题现象常见原因解决思路递归无限进行最终栈溢出递归出口条件写错或分区返回的基准下标没有落在[left, right]内检查if (left right) return;确认partition返回值一定在可选区间内排序结果中某些元素丢失或重复分区时把基准值覆盖但没有在最后放回来使用挖坑法时注意保存 pivot并在两指针相遇的位置填回数组越界访问内层 while 没有加left right条件右指针跑过头内层循环必须同时判断左右指针位置有序数组排序极慢固定选择首尾元素作为基准分区严重不平衡使用随机基准或三数取中法Java 中大量相同元素排序效率低普通两路分区无法快速处理重复元素考虑三路快速排序或直接使用 JDK 内置排序递归深度过大导致栈溢出最坏情况下递归深度接近 n尝试尾递归方式只递归较短的一侧另一侧用迭代处理选择合适的基准策略9.2 一个容易忽略的错误示例假设在挖坑法内层循环里漏掉left right代码会变成while (arr[right] pivot) { right--; }当左指针已经在数组中间而右指针持续向左越过左指针甚至越过区间边界时会访问到错误内存最终导致程序崩溃或结果错误。类似场景在 Java 中则可能抛出ArrayIndexOutOfBoundsException。排查这类问题时不要只盯着某一行代码建议先用小数组比如 3 到 5 个元素在纸上画出每次left、right的变化。多数问题会在这个过程中暴露。9.3 单元测试是排查的好帮手在实际项目中手动打印数组验证效率不高建议为排序函数编写基础的单元测试。测试数据应覆盖这几类随机乱序数组。已经有序的数组。完全逆序的数组。所有元素都相同的数组。包含负数、正数和零的数组。只有一个元素的数组。空数组。用这些边界场景去跑排序函数很多隐藏问题会很快暴露。数组越界和无法退出的问题在空数组和单元素数组中特别容易被发现。10. 面试与工程中的复盘建议快速排序是算法面试里的高频题目。面试官问它往往不只是想要一段能跑的代码更想通过几个连续问题判断你对算法过程的理解深度。建议你复盘时先不看代码拿[5, 3, 8, 4, 2, 7, 1, 6]自己在纸上画一遍分区过程遇到指针移动不对时再对比代码。这个“脱离代码画动画”的练习比反复抄代码有效得多。第二步是练习手写一个基础版快速排序要求能做到逻辑清楚、边界正确。不要急着背优化版本先把递归出口、分区返回下标、左右子区间划分写对。第三步才是理解变体和优化比如为什么Arrays.sort()不用普通快速排序为什么大量重复元素会慢三路快排如何改进归并排序与快速排序在稳定性、空间复杂度上的取舍。工程开发中如果只是给业务数据排序优先使用语言或框架提供的高性能排序方法。Java 使用Arrays.sort()C 语言标准库有qsort()Python 有内置的list.sort()。自己实现快排主要用于学习、面试、中间件底层开发或者处理一些标准库无法覆盖的特殊排序需求。真正吃透快速排序不是记住一行pivotIndex 1而是能在心里浮现出整个动态过程两个指针如何相向而行坑如何被反复填上递归如何一层层拆解数组又一层层返回结果。有了这种“动画感”你再去学归并排序、堆排序、三路快排都能比原来轻松不少。
快速排序动画图解：递归分治与C/Java实现原理详解
提到排序算法快速排序基本是笔试、面试和工程实战里出场率最高的一个。很多朋友第一次看代码时感觉逻辑还能懂但一旦问到“为什么这样交换”“基准元素到底怎么放回去”“递归之后数组为什么就对了”就容易卡住。为了讲清楚本文用“动画思路”来拆解快速排序把每一次指针移动、每一轮交换都当作画面来呈现同时给出 C 语言和 Java 的完整可运行代码帮助你从原理到实现一次打通。如果你准备算法面试或者想彻底告别“背代码但画不出过程”的状态这篇文章很适合你。读完你会掌握快速排序的完整流程、分区函数的不同写法、时间复杂度的推导以及有序数组下性能退化的原因和优化手段。1. 为什么快速排序值得反复看1.1 快速排序解决什么问题排序是编程里最基础的需求之一给定一组无序数据按照从小到大或从大到小排列。快速排序是目前使用最广泛的排序算法之一很多编程语言内置排序函数的底层都包含快速排序的思想。打个比方如果排序是一所学校要给全校学生按照身高排队冒泡排序的做法是相邻两个人不断比较、交换像气泡一样把高个子慢慢推到后面。快速排序的做法则更像“分组管理”先找出一个参考身高的人让比他矮的都站到左边比他高的都站到右边。这样一来这个参考人已经站在了最终位置左侧和右侧的人只需要在各自小组里继续重复同样的动作即可。在真实工程中快速排序之所以受欢迎是因为它在多数情况下能做到 O(n log n) 的平均时间复杂度而且排序过程是在原数组内部完成不需要额外的大块内存属于原地排序。1.2 一对关键概念递归与分治快速排序的实现离不开两个重要的算法思想分治Divide and Conquer和递归Recursion。所谓分治就是把一个大规模问题拆分若干个规模更小、结构相似的子问题分别解决后再合并结果。快速排序把数组拆成左半部分所有元素都小于等于基准。一个基准元素它已经在正确的最终位置。右半部分所有元素都大于等于基准。由于左右两部分继续使用同样的排序逻辑就非常适合用递归来实现。每次递归调用做同一件事把当前区间内的数据分成左右两块让基准元素归位。这里有一个初学者容易绕晕的点快速排序不是“先整体排好再递归处理左右”而是“每轮只保证基准元素的位置左右两侧还乱着靠递归一点点把乱的部分也理清”。这种动态过程用文字描述不如“画面感”直观所以接下来我们用多个详细步骤来拆解。2. 快速排序整体流程拆解2.1 三步循环快速排序的主流程可以用三步来概括选择一个基准值pivot。对当前区间做分区partition把小于基准的值放到左边大于基准的值放到右边并把基准放到它最终的位置。对基准左边和右边的子区间递归执行同样的步骤。其中第 2 步是快速排序的核心。做完一次分区后数组并不会立刻有序但基准元素不会再去动它因为它的位置已经正确。左右两侧继续递归不断缩小范围直到每个子区间只剩一个元素或者为空整个数组就自然有序了。递归仍然不好理解的同学可以把“只剩下一个元素”看作递归出口。一个元素本身已经有序不需要再排序此时函数直接返回不再向下递归。2.2 动画视角看一轮完整分区为了看清动态过程我们拿一个实际数组来演示。假设现在要对下面这个数组从小到大排序[5, 3, 8, 4, 2, 7, 1, 6]我们选择第一个元素 5 作为基准值 pivot。目标是把小于 5 的放到左边大于 5 的放到右边并且让 5 落到正确位置。我采用“挖坑填数”的方式演示这也是最容易”脑补“成动画的一种分区方式第一步把基准值 5 从数组里取出来相当于位置 0 留下一个“坑”坑, 3, 8, 4, 2, 7, 1, 6从右往左找小于 5 的数。右边第一个数是 6不满足继续往左遇到 1满足条件。把 1 填到左边的坑里1, 3, 8, 4, 2, 7, 坑, 6此时右边原来放 1 的位置变成了新的坑。接下来从左往右找大于 5 的数。左边已经是 1、3都不大于 5继续向右遇到 8满足条件。把 8 填到右边的坑里1, 3, 坑, 4, 2, 7, 8, 6此时左边原来放 8 的位置又变成坑。继续从右往左找小于 5 的数。当前右边是 7不满足继续向左遇到 2满足条件。把 2 填到左边的坑1, 3, 2, 4, 坑, 7, 8, 6接着从左往右找大于 5 的数。4 不大于 5继续往右左右指针相遇在位置 4。此时把基准值 5 填进这个坑1, 3, 2, 4, 5, 7, 8, 6这一轮结束后5 左边都是小于它的数5 右边都是大于它的数。5 所在的下标是 4它已经位于最终位置不需要再移动。之后只需要对左边区间[1, 3, 2, 4]和右边区间[7, 8, 6]分别递归执行相同操作。把上面过程在脑中“动”起来你会发现整个过程就像左右两个指针在交替寻找可以填坑的元素这也是“动画讲解快速排序”时最核心的画面。2.3 递归出口很关键递归函数必须有出口否则会无限调用直到栈溢出。快速排序的递归出口是区间左边界大于等于右边界说明当前区间元素个数为 0 或 1无需排序。例如处理[7, 8, 6]时再次分区后得到[6]和[8]两个子区间都只有一个元素下一轮递归直接返回。算法不再继续切分最终整个数组完成排序。3. 基准元素的选择影响效率3.1 固定选第一个或最后一个元素最简单的基准选择策略是固定取当前区间的第一个元素或最后一个元素。代码写起来方便但存在明显缺点如果数组本身接近有序每次选到的基准很可能正好是当前区间的最小值或最大值分区结果会非常不平衡导致快速排序退化为 O(n²)。举一个例子数组已经是[1, 2, 3, 4, 5]固定选第一个元素 1 作为基准。分区后左边为空右边是[2, 3, 4, 5]每次只能减少一个元素递归深度变成 n总比较次数接近 n (n-1) ... 1也就是 O(n²)。所以固定选基准虽然代码最简但在生产级实现里并不推荐。3.2 随机选基准改进思路之一是随机选一个下标作为基准。随机化之后数组有序时不再每次都选中最小或最大值出现最坏情况的概率大幅降低。实现时需要注意选随机下标后可以把这个下标的值和区间第一个元素交换这样后续分区逻辑仍然按照原来的模板走不需要额外修改。3.3 三数取中法工程中最常用的折中方案是“三数取中”Median of Three从区间左端、中间、右端取出三个元素选择数值居中的那个作为基准。例如区间是[left, mid, right]分别对应9, 1, 5那么基准应该取中间的 5。这个方案既避免了纯随机带来的不确定性又能在有序数组上得到比较好的分区效果。JDK 的排序实现、很多标准库内部都会考虑类似的策略。对普通学习来说直接用第一个元素作为基准即可因为重点在于理解算法过程但在实际产品代码里最好至少加上随机化或三数取中。4. 分区函数快速排序的灵魂4.1 分区负责什么分区函数要做的事是在一个数组中选定一个基准然后通过比较和交换把数组整理成“左小右大”的结构最后返回基准元素的下标。这个返回值非常重要。主排序函数拿到基准下标之后就可以确定下一次递归的范围左子区间[left, pivotIndex - 1]右子区间[pivotIndex 1, right]很多初学快速排序的同学会写错原因往往不是整体框架而是分区函数里指针移动和交换的顺序写错。4.2 两种常见的分区思路业界有几类分区写法这里介绍最主流的两种。第一种是“挖坑法”。前面演示用到的就是这种方法。实现时先保存基准值相当于把基准位置挖成一个坑然后右指针向左找小于基准的值来填左边的坑左指针向右找大于基准的值来填右边的坑直到两个指针相遇最后把基准值放进相遇位置。第二种是“Lomuto 分区法”。这是很多算法教材里常见的写法代码更短。它通常选最后一个元素作为基准用两个指针 i 和 j 同时从左往右扫描j 负责遍历每个元素。i 负责指向“小于等于基准的区域”的末尾。当 j 遇到小于等于基准的元素时把 i 后移一位并交换 i 与 j 位置的值。遍历结束后将基准与 i1 位置的值交换。无论使用哪种分区写法关键点都是分区完成后基准前面的元素都满足小于等于基准基准后面的元素都满足大于等于基准。4.3 看动画时重点看的三个细节很多快速排序动画里不同颜色的小方块代表不同元素两根指针或两个下标在不断移动。想从动画里真正学到东西建议重点看三个细节第一坑的位置如何从左跳到右、又从右跳回左。这是理解挖坑法的钥匙。第二为什么两个指针最终会相遇。因为每次填坑后区间会不断向中间收缩坑的位置也在变化最终左右指针落在同一个位置这个位置就是基准的归宿。第三递归结束后数组如何逐渐从“局部正确”变成“整体正确”。每一轮分区只保证一个基准归位但因为递归的作用所有元素都会依次归位。5. C 语言实现快速排序5.1 使用挖坑法的 C 代码先来一段常见且易于理解的 C 语言实现。这个版本使用第一个元素作为基准采用挖坑法分区。#include stdio.h // 分区函数对 arr[left..right] 进行分区返回基准最终下标 int partition(int arr[], int left, int right) { int pivot arr[left]; // 挖坑先把基准值保存起来 while (left right) { // 从右往左找小于基准的值 while (left right arr[right] pivot) { right--; } // 找到后填到左边的坑 arr[left] arr[right]; // 从左往右找大于基准的值 while (left right arr[left] pivot) { left; } // 找到后填到右边的坑 arr[right] arr[left]; } // left 和 right 相遇把基准值放入坑中 arr[left] pivot; return left; } // 快速排序递归函数 void quickSort(int arr[], int left, int right) { if (left right) { return; } int pivotIndex partition(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex 1, right); } // 打印数组 void printArray(int arr[], int size) { for (int i 0; i size; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {5, 3, 8, 4, 2, 7, 1, 6}; int size sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, size); quickSort(arr, 0, size - 1); printf(排序后); printArray(arr, size); return 0; }运行这段代码控制台会输出排序前5 3 8 4 2 7 1 6 排序后1 2 3 4 5 6 7 85.2 结合动画再读一遍代码看这段 C 代码的时候一定要把partition函数里的while (left right)想象成两个左右移动的指针。外层while (left right)是不断收缩区间。只要左右指针没有相遇说明还没有确定基准的位置。内部第一个while让右指针向左移动直到找到比基准小的数字内部第二个while让左指针向右移动直到找到比基准大的数字。比较常见的出错点是漏写内层循环里的left right条件。如果漏写右指针可能会越过左指针导致基准位置错误甚至访问数组越界。因此在写代码时这两个内层判断不能省。5.3 C 语言实现注意事项C 语言中数组作为函数参数时会退化为指针因此quickSort内不要试图直接计算数组长度必须在调用处把right下标传入。示例代码里用sizeof(arr) / sizeof(arr[0])计算长度也是在main函数中完成的并没有传给子函数后再次计算。6. Java 实现快速排序6.1 基础版 Java 代码Java 实现同样基于递归和分区。下面这段代码使用 Lomuto 分区法基准选择当前区间最后一个元素。相比挖坑法它的代码更紧凑也是很多算法教材采用的版本。import java.util.Arrays; public class QuickSort { // Lomuto 分区选最后一个元素作为基准 public static int partition(int[] arr, int low, int high) { int pivot arr[high]; int i low - 1; // i 指向小于等于基准的那一段的末尾 for (int j low; j high; j) { if (arr[j] pivot) { i; // 将较小的元素交换到前面 int temp arr[i]; arr[i] arr[j]; arr[j] temp; } } // 将基准放到正确位置 int temp arr[i 1]; arr[i 1] arr[high]; arr[high] temp; return i 1; } public static void quickSort(int[] arr, int low, int high) { if (low high) { int pivotIndex partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex 1, high); } } public static void main(String[] args) { int[] arr {5, 3, 8, 4, 2, 7, 1, 6}; System.out.println(排序前 Arrays.toString(arr)); quickSort(arr, 0, arr.length - 1); System.out.println(排序后 Arrays.toString(arr)); } }运行后输出排序前[5, 3, 8, 4, 2, 7, 1, 6] 排序后[1, 2, 3, 4, 5, 6, 7, 8]6.2 Lomuto 分区的过程如何用动画理解Lomuto 分区可以想象成一只手在维护“已经确认小于基准”的边界。指针 j 像扫描镜头从 low 一路滑到 high 前一个位置。每扫描到一个小于等于基准的数值它就把这个数值和“边界后面的元素”交换也就是把 i 向后移动一格。这个过程像把小于基准的小球不断捡到左边篮子里最后再把基准放到篮子的右边。当数组中有很多重复元素时建议使用而不是。这里不展开读者可以尝试把 Lomuto 实现里的改成并运行包含重复元素的数组观察结果差异这有助于理解基准的归位条件。6.3 Java 泛型与对象排序思路上面代码只处理int[]。实际项目中Java 经常需要对对象数组或集合排序。更方便的方式是依赖Comparable或Comparator。例如你可以把基准比较提取成一个方法让数组元素类型变成泛型T配合比较器决定谁在前谁在后。不过工程实现中直接使用Arrays.sort()或Collections.sort()已经足够高效没有必要为普通业务数据手写快速排序。自己实现快速排序更多用于算法学习、面试考察和特殊场景的定制优化。7. 时间复杂度、空间复杂度与稳定性7.1 时间复杂度如何推导快速排序的时间复杂度与基准选择密切相关。在理想情况下每次分区都能把数组分成两个长度大致相等的部分。每层递归对所有元素进行一次遍历单层时间是 O(n)。递归深度是 O(log n)因此总时间复杂度是 O(n log n)。在最坏情况下每次基准都是当前区间的最小值或最大值导致分区后一侧为空、另一侧有 n-1 个元素。递归深度退化为 O(n)总比较次数约为 n (n-1) ... 1因此时间复杂度退化为 O(n²)。所以快速排序的平均时间复杂度是 O(n log n)最坏时间复杂度是 O(n²)。7.2 空间复杂度快速排序的空间主要消耗在递归调用产生的栈空间上。理想情况下递归深度为 O(log n)因此空间复杂度为 O(log n)。最坏情况下递归深度为 O(n)空间复杂度也退化为 O(n)。很多人误以为快速排序是完全原地排序所以空间复杂度是 O(1)这并不准确。快速排序虽然没有大量额外数组但递归调用本身会占用调用栈不能简单看作 O(1)。7.3 稳定性为什么重要又为什么快排不满足稳定排序的定义是如果两个元素的原始顺序本就符合业务要求当它们的排序关键字相等时排序后相对顺序保持不变。在整数排序场景中稳定性看似无关紧要但在多字段排序时比如先按时间排序、再按优先级排序稳定的排序能保留前一轮的排序结果。快速排序是不稳定排序。原因是分区过程中可能会把右边小于基准的元素交换到左边而这些交换可能导致相等元素的相对位置发生变化。看一个简单例子数组为[5a, 3, 5b, 2]如果基准选择某个值后需要把靠后的5b与比它小的元素交换两个相等元素5a、5b的先后顺序就可能被改变。因此当业务明确要求稳定排序时应该选择归并排序等稳定算法。8. 快速排序的退化场景与常见优化8.1 什么情况下性能会退化最容易导致性能退化的场景是输入数组已经基本有序或完全有序同时又固定选择第一个或最后一个元素作为基准。此时每次分区只拿掉一个元素递推关系接近 T(n) T(n-1) O(n)累加得到 O(n²)。除了有序数组大量重复元素也会带来性能问题。普通分区法遇到全部元素相等时一侧可能收集全部元素另一侧为空同样会造成不必要的递归和比较。8.2 三路快速排序针对大量重复元素常见优化是“三路快速排序”3-Way QuickSort。普通快速排序把数组分成两部分小于等于基准和大于等于基准三路快速排序则分成三个区间小于基准的部分。等于基准的部分。大于基准的部分。处理完一轮后所有等于基准的元素都已经处在一个连续的中间区间里不需要再参与后续递归。这样遇到大量重复元素时递归处理的区间大幅缩小性能有明显提升。Java 的Arrays.sort()对基本类型数组使用双基准快速排序Dual-Pivot QuickSort它把数组分成三段区间思想与三路快排有相通之处都能尽量避免重复元素带来的性能下降。8.3 工程实现中的混合策略真实的标准库里很少只依赖基本快速排序来解决所有情况。常见的混合策略包括递归区间较小时改用插入排序因为小数组上插入排序的常数开销更小。递归深度超过一定阈值时改用堆排序防止有序输入导致 O(n²)。基准选择使用三数取中或随机化。这种“检测到递归退化就换算法”的思路被称为 Introsort。C 标准库的std::sort就综合使用了快排、插入排序和堆排序的思想。对读者来说理解这些优化不是为了记住复杂代码而是为了遇到性能问题时知道从哪里入手分析。9. 快速排序常见错误与排查思路9.1 高频错误现象与解决方案问题现象常见原因解决思路递归无限进行最终栈溢出递归出口条件写错或分区返回的基准下标没有落在[left, right]内检查if (left right) return;确认partition返回值一定在可选区间内排序结果中某些元素丢失或重复分区时把基准值覆盖但没有在最后放回来使用挖坑法时注意保存 pivot并在两指针相遇的位置填回数组越界访问内层 while 没有加left right条件右指针跑过头内层循环必须同时判断左右指针位置有序数组排序极慢固定选择首尾元素作为基准分区严重不平衡使用随机基准或三数取中法Java 中大量相同元素排序效率低普通两路分区无法快速处理重复元素考虑三路快速排序或直接使用 JDK 内置排序递归深度过大导致栈溢出最坏情况下递归深度接近 n尝试尾递归方式只递归较短的一侧另一侧用迭代处理选择合适的基准策略9.2 一个容易忽略的错误示例假设在挖坑法内层循环里漏掉left right代码会变成while (arr[right] pivot) { right--; }当左指针已经在数组中间而右指针持续向左越过左指针甚至越过区间边界时会访问到错误内存最终导致程序崩溃或结果错误。类似场景在 Java 中则可能抛出ArrayIndexOutOfBoundsException。排查这类问题时不要只盯着某一行代码建议先用小数组比如 3 到 5 个元素在纸上画出每次left、right的变化。多数问题会在这个过程中暴露。9.3 单元测试是排查的好帮手在实际项目中手动打印数组验证效率不高建议为排序函数编写基础的单元测试。测试数据应覆盖这几类随机乱序数组。已经有序的数组。完全逆序的数组。所有元素都相同的数组。包含负数、正数和零的数组。只有一个元素的数组。空数组。用这些边界场景去跑排序函数很多隐藏问题会很快暴露。数组越界和无法退出的问题在空数组和单元素数组中特别容易被发现。10. 面试与工程中的复盘建议快速排序是算法面试里的高频题目。面试官问它往往不只是想要一段能跑的代码更想通过几个连续问题判断你对算法过程的理解深度。建议你复盘时先不看代码拿[5, 3, 8, 4, 2, 7, 1, 6]自己在纸上画一遍分区过程遇到指针移动不对时再对比代码。这个“脱离代码画动画”的练习比反复抄代码有效得多。第二步是练习手写一个基础版快速排序要求能做到逻辑清楚、边界正确。不要急着背优化版本先把递归出口、分区返回下标、左右子区间划分写对。第三步才是理解变体和优化比如为什么Arrays.sort()不用普通快速排序为什么大量重复元素会慢三路快排如何改进归并排序与快速排序在稳定性、空间复杂度上的取舍。工程开发中如果只是给业务数据排序优先使用语言或框架提供的高性能排序方法。Java 使用Arrays.sort()C 语言标准库有qsort()Python 有内置的list.sort()。自己实现快排主要用于学习、面试、中间件底层开发或者处理一些标准库无法覆盖的特殊排序需求。真正吃透快速排序不是记住一行pivotIndex 1而是能在心里浮现出整个动态过程两个指针如何相向而行坑如何被反复填上递归如何一层层拆解数组又一层层返回结果。有了这种“动画感”你再去学归并排序、堆排序、三路快排都能比原来轻松不少。
