快速排序可能是面试中出现频率最高的排序算法没有之一。它不只是大学课堂里的必考知识点更是工程实践和算法竞赛中绕不开的基础工具。很多人能背出“选基准、分两边、递归排序”这三句话但写出来的代码却总是隐含各种边界问题排序结果不对、数据量稍大就栈溢出、接近有序的数组性能直接崩甚至死循环。这篇内容会从分治思想讲起完整给出可运行的Java实现补充常见的优化手段并分享我几年里反复写快速排序踩过的坑和排查思路直接对标面试和实战场景无论是正准备面试的开发者还是工作中需要自己实现排序逻辑的人都可以跟着复现一遍。1. 快速排序的底层逻辑分治思想与核心概念快速排序之所以叫“快速”一靠分治策略二靠partition的原地交换。这两个字背后是一整套值得反复琢磨的设计思想而不仅仅是几行代码。1.1 分治思想把大问题拆到不能再拆分治思想说白了就是大问题不好解就切成小问题逐个解决。生活里最典型的例子是整理书架——你不会把所有书从头到尾重新排一遍而是先按类别分成小说、历史、技术、育儿几堆再对每一堆内部局部整理。快速排序做的就是类似的事。从算法结构上看快速排序每次选择一个基准元素pivot通过一趟遍历把数组分成两段左边所有元素都小于等于基准右边所有元素都大于等于基准。基准元素在完成这一趟之后就落到了它最终应该在的位置上。然后问题就缩小成对基准左边和右边两个子区间分别做同样的操作递归下去每个子区间都只剩一个元素时整个数组自然有序。这里有一个微妙但至关重要的认知快速排序并不是像冒泡排序那样每轮比较相邻元素逐步“冒”出顺序而是通过不断的局部重排让每个元素在递归过程中被放到最终位置。每一趟partition能确定一个元素的最终位置递归调用后再确定下一批最终所有位置都确定排序就结束了。这也是它区别于归并排序的地方——归并排序需要额外的辅助数组合并而快速排序是纯原地操作空间占用天然就有优势。1.2 一趟partition到底做了什么partition是快速排序的核心动作。以升序排序为例它的目标很简单选一个元素当基准一趟处理之后所有比基准小的元素都移到基准左边所有比基准大的元素都移到基准右边基准自己居中。我见过的初学者最容易犯的认知错误是把partition想象成“比较交换后整体排序”——事实上它只做局部整理并不追求一趟结束后整个区间有序。左边那半内部还是乱的右边那半内部也是乱的但这不重要。重要的是基准找到了自己的最终位置剩下的问题被拆成了两个互不干扰的独立子问题。这种“不求全部到位只求分而治之”的思路才是快速排序能在大多数情况下表现出优异性能的关键。从代码层面看一趟partition通常会维护两个指针一个负责扫描当前元素一个负责标记“小于基准区”的边界。每发现一个比基准小的元素就把它和边界后的第一个元素交换然后扩展边界。扫描结束后把基准交换到边界位置一趟partition就算完成。整个过程只遍历一次子区间时间复杂度是O(n)没有额外空间开销。1.3 复杂度分析为什么平均是O(n log n)很多人在理解快速排序复杂度时只记结论没有深挖过程导致面试时一旦被追问就会卡壳。我用自己的理解来拆一遍。每一趟partition都要扫描当前区间的所有元素这个扫描的代价是O(n)。关键在于递归层数是多少最优情况每次基准恰好把区间对半分。递归层数就是log₂n层每层扫描的总代价是O(n)所以总体是O(n log n)。这很好理解类似一颗平衡二叉树的深度。平均情况基准落在任何位置的概率相等。可以证明在随机数据下期望的递归层数依然是O(log n)量级。即便基准偶尔偏离中线只要不是每次都极端偏离整体性能依然接近O(n log n)。最坏情况每次基准都是当前区间的最大值或最小值。这意味着每趟partition只把区间缩小1个元素递归层数就变成了n层每层扫描代价O(n)总体退化为O(n²)。最典型的触发场景就是已经有序的数组如果每次固定取区间最后一个元素当基准就会出现这种灾难。情况时间复杂度空间复杂度递归栈触发条件平均O(n log n)O(log n)随机/打乱数据最优O(n log n)O(log n)每次基准对半分最坏O(n²)O(n)有序数据 固定端基准空间复杂度方面很多人容易忽略快速排序是原地排序不需要额外的辅助数组但递归调用本身会占用系统栈空间。理想状态下递归深度是O(log n)最坏退化成O(n)。这也是后文要讲的“随机化基准”和“尾递归优化”的核心价值所在。2. 快速排序Java实现从零手写一份可运行代码原理讲清楚之后来看代码。这里给出最经典的递归实现采用Lomuto分区方案注释逐个变量解释方便对照理解。2.1 经典递归实现Lomuto分区public class QuickSort { public static void quickSort(int[] arr) { if (arr null || arr.length 2) { return; } quickSort(arr, 0, arr.length - 1); } private static 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); } private static int partition(int[] arr, int left, int right) { // 取区间最后一个元素作为基准 int pivot arr[right]; // i 记录“小于基准区域”的边界初始在左边界之前 int i left - 1; // j 从左向右扫描遇到小于等于基准的元素就交换到左侧区域 for (int j left; j right; j) { if (arr[j] pivot) { i; swap(arr, i, j); } } // 扫描结束后把基准放回两个区域的中间 swap(arr, i 1, right); return i 1; } private static void swap(int[] arr, int a, int b) { int tmp arr[a]; arr[a] arr[b]; arr[b] tmp; } public static void main(String[] args) { int[] arr {9, 3, 7, 1, 5, 8, 2, 6, 4}; quickSort(arr); for (int num : arr) { System.out.print(num ); } } }这段代码可以直接复制运行。我建议初学的人不要直接背而是在纸上模拟一遍partition过程取数组{9, 3, 7, 1, 5}手动把每一轮i、j的变化写出来很快就能理解“边界指针”到底在做什么。2.2 边界条件与指针移动的细节代码写出来容易写对却需要抠几个核心细节。我挑了最容易出错的几个点单独说。递归终止条件if (left right)判断的是“区间内没有元素或只有一个元素”。很多人写成left right这在一个元素的场景下没问题但当区间为空比如partition把基准放到了最左端导致pivotIndex - 1 left时就会漏掉。用最为稳妥这是我在实际调试中踩过多次的坑。扫描指针的起点int i left - 1是Lomuto分区方案的精髓。i指向的是“当前已经发现的小于基准区域”的最右边界初始时这个区域是空的所以是left - 1。每找到一个小于等于基准的元素先把i向右挪一格再把该元素交换进来。这样到最后i的左边全是小于等于基准的值i1的位置就是基准该待的地方。为什么用而不是如果基准元素在区间中出现多次用可以把相等的元素也交换到左侧。虽然快速排序不是稳定排序这种写法也无法保证相等元素的相对顺序但可以避免一种尴尬的场景区间里所有元素都等于基准时如果只用分区函数会把整个区间都划到“大于区”导致两边完全不平衡。用则能保证至少一半元素在基准左边。交换下标要区分清楚Lomuto分区中第一个swap是对扫描到的元素与边界后元素做交换第二个swap才是把基准放到最终位置。初学者最常犯的错误是漏掉或者写反第二个swap导致基准位置根本不在它应该在的地方递归排序自然完全错误。2.3 Hoare分区另一种更快的写法Lomuto分区逻辑简单适合讲课和面试表达但它的交换次数在实际测试中会比Hoare分区多。Hoare分区的思路和Lomuto截然不同它不是单指针扫描后统一放基准而是用双指针从两端向中间逼近只要发现左侧有比基准大的元素、右侧有比基准小的元素就直接交换这一对直到两个指针相遇。private static int partitionHoare(int[] arr, int left, int right) { int pivot arr[left]; int i left - 1; int j right 1; while (true) { // 从左往右找第一个不小于基准的元素 do { i; } while (arr[i] pivot); // 从右往左找第一个不大于基准的元素 do { j--; } while (arr[j] pivot); if (i j) { return j; } swap(arr, i, j); } }使用Hoare分区时需要注意两点第一递归调用变成了quickSort(arr, left, j)和quickSort(arr, j 1, right)因为j既可能是分界点也可能就是基准所在位置这取决于最终指针相遇方式第二基准选择通常取arr[left]或arr[mid]配合后文的三数取中效果更好。实测Hoare分区的交换次数约为Lomuto的1/3对大数据量有明显改善但代码理解和调试的难度也更高。我的建议是面试表达用Lomuto工程优化用Hoare两者都值得手写一遍。3. 性能优化三板斧让快速排序更稳手写快速排序不难难的是写得“稳”。排序算法最怕的就是数据分布极端以下三个优化手段是目前业界最常用、也最经过验证的。3.1 随机化基准与三数取中固定取最后一个元素当基准是快速排序性能崩溃的根源。设想一个已经升序排列的数组pivot arr[right]永远是最大值分区函数一趟扫描后基准还在最右边左边剩下n-1个元素再递归一层又重复同样的情况。实测数据量到5000以上时就能明显感知到卡顿1万以上时递归深度会超过默认栈限制直接抛StackOverflowError。解决思路有两个方向随机化基准是最简单的应对。在partition之前随机选一个下标rand把arr[rand]和arr[right]交换再用原来的Lomuto逻辑。这样无论输入数据本身是什么分布基准落在任何位置的概率都均等最坏情况的出现概率被压缩到几乎不可能。Random random new Random(); int rand left random.nextInt(right - left 1); swap(arr, right, rand);三数取中是更工程化的方案。从left、mid、right三个位置取出元素取大小居中的那个作为基准。这样做的好处是对于已经有序的数组三数取中能直接选中正中间的元素一趟分区就把数组对半劈开最坏情况被彻底规避。JDK底层的Arrays.sort在排序基本类型数组时也采用了类似思想。我个人的建议是两者都加。随机化保护了“不知情”的恶意输入三数取中保证了常规有序数据的效率组合使用效果最好。3.2 小数组切换到插入排序这可能是理解的人最少但收益最明显的一个优化。快速排序的递归在区间很小的时候比如只剩十几二十个元素递归调用的开销、函数栈的压入弹出显得非常不划算。而插入排序在小规模数据上因为极少的比较次数和优异的局部性反而跑得更快。业内常见的阈值在[7, 20]之间。当right - left 1小于等于这个阈值时直接改用插入排序处理当前区间而不是继续递归快速排序。private static void quickSort(int[] arr, int left, int right) { if (right - left 1 10) { insertionSort(arr, left, right); return; } // 其他逻辑不变 }插入排序的实现在这里有一个优化细节——把普通的逐个插入改成在一个小区间内做局部调整可以减少交换次数。不过对于10~16大小的区间怎么写性能都差不多。我实测下来阈值取10左右在随机大数据量下通常是5%~10%级别的性能提升幅度不算夸张但几乎是零成本和零风险。3.3 尾递归优化与并行化快速排序的两个递归调用中第二个调用处理右半部分可以用循环替代这是标准的尾递归优化手段。原理很简单既然排序完左边之后还要处理右边不如把左边交给递归右边留在当前循环继续执行省去一层递归栈的深度。private static void quickSort(int[] arr, int left, int right) { while (left right) { int pivotIndex partition(arr, left, right); // 递归处理左半部分 quickSort(arr, left, pivotIndex - 1); // 循环处理右半部分 left pivotIndex 1; } }这里的思路是让递归深度在整个过程中只依赖“每次都选较短的那一半”来降低最坏深度。更严格的做法是每次都先比较左半和右半的大小永远先递归短的那一半这样即使所有分区都极端不平衡递归深度也保持在O(log n)。并行化则是多核时代的一个自然延伸。排序的本质是分治分治天然适合并行左右两个子区间互相独立把其中一个交给另一个线程处理即可。Java里可以借助ForkJoinPool或CompletableFuture实现。不过要注意并行化只在数据量达到几十万以上时有明显收益数据量小的时候线程调度的开销反而会拖慢速度。工程上JDK的并发排序Arrays.parallelSort底层就使用了类似思路当数组长度超过一个阈值时启用多线程快速排序阈值大约在8192左右。4. 实战中的坑快速排序常见问题排查即便是经验丰富的开发者手写快速排序时也会遇到各种诡异问题。这里把我见过和踩过的坑整理成一份排查清单。4.1 死循环是怎么产生的死循环最典型的症状是程序久久不结束CPU占用100%。常见原因有两个一是递归基写错。如果partition返回的基准下标在某些场景下等于left或right而递归调用时又把同样的区间再传进去就会无限递归。比如用Lomuto分区且pivot选到了当前区间的最小值基准会被交换到左边界这时左半区间是空的还好但如果递归条件写的是quickSort(arr, left, pivotIndex)而不是pivotIndex - 1就会把这个空区间重新处理一遍无限循环。二是分区逻辑在重复元素上失效。比如Hoare分区中如果没有处理等于基准的元素两个指针可能互相交错不退出导致无限循环。解决方法是严格使用while(arr[i] pivot)和while(arr[j] pivot)的写法把等于基准的元素交给循环体内的交换逻辑去处理让两个指针能够继续推进并最终相遇。排查死循环时我一般会在partition入口打印区间左右边界如果发现连续多次调用的是同一个区间就说明递归条件或分区返回值有逻辑问题。4.2 栈溢出与递归深度栈溢出的本质是递归层数太深而快速排序的递归深度直接取决于基准是否把区间对半分。固定取端点作为基准时遇到有序数组或逆序数组递归深度就是nJava默认线程栈容量下1万左右的数据量就可能抛出StackOverflowError。解决方案按优先级排列三数取中或随机化基准从根源上保证分区的平衡性尾递归优化把右半部分的递归改为循环递归深度只取决于较长调用链手动扩大栈容量通过-Xss参数调整JVM线程栈大小但这只是临时方案不能依赖改用非递归实现用显式栈保存待处理区间彻底摆脱系统栈限制。我建议在面试或工程实现中至少做到前两条基本能覆盖所有正常场景。4.3 不是稳定排序的后果快速排序是不稳定的。所谓稳定是指排序前后相等元素的相对顺序保持不变。比如一个学生列表先按班级排好再按成绩排序如果成绩相同的两个学生原本前者在前排序后可能就变成后者在前了。什么时候需要稳定性业务场景中最典型的是多关键字排序。假设你有一个商品列表需要先按销量降序、再按上架时间升序排列那么第二次排序必须保持第一次排序的相对顺序——哈希表存储的对象顺序敏感、日志场景按时间戳排序等同样如此。如果需要稳定排序且有空间换时间的余地首选归并排序如果必须原地且注重效率可以考虑稳定版本的快速排序变体但实现复杂度较高。日常开发中没必要强制使用不稳定的快速排序来满足稳定性需求选择合适的算法更重要。4.4 快速排序不适用的场景这不仅是一个技术问题还是一个决策问题。我见过不少人在数据量只有几十个元素时也强行套一个快速排序属于性能过度设计。结合几个具体场景来分析数据量极小50插入排序的比较次数更少代码更简单性能优于快速排序。几乎有序的数组如果对原始数据做优化不足的快速排序复杂度会退化到O(n²)此时插入排序、冒泡排序甚至都可以做到接近O(n)。基准策略设计良好的快速排序才能应对这种场景。极其庞大的数据TB级别无法完全载入内存通常使用外排序多路归并来处理而不是内存中的快速排序。对稳定性有要求的业务场景前面已述用归并排序或Collections.sort这类稳定实现更合适。链表排序快速排序依赖下标和随机访问链表的随机访问是O(n)强行用快速排序效率极低链表排序使用归并排序是最优选择。遇到这些场景时应该有意识跳出“快排就是最优”的惯性思维。算法选择的关键是数据特征和业务需求不是算法本身的知名度。5. 性能实测与应用场景分析5.1 基准测试的方法与结果解读写排序算法不能只看代码“感觉对”需要用数据说话。我习惯用十万规模的随机数组做一次简单基准测试每轮测试至少运行5次取中位数避免JVM热点编译和GC带来干扰。一个简单可复现的测试框架public class SortBenchmark { public static void main(String[] args) { int[] sizes {10_000, 100_000, 1_000_000}; for (int n : sizes) { int[] random generateRandomArray(n); int[] sorted generateSortedArray(n); test(随机数据, random); test(有序数据, sorted); } } private static void test(String label, int[] arr) { int[] copy Arrays.copyOf(arr, arr.length); long start System.nanoTime(); QuickSort.quickSort(copy); long end System.nanoTime(); System.out.println(label , 耗时 (end - start) / 1_000_000 ms); } private static int[] generateRandomArray(int n) { Random random new Random(42); int[] arr new int[n]; for (int i 0; i n; i) { arr[i] random.nextInt(); } return arr; } private static int[] generateSortedArray(int n) { int[] arr new int[n]; for (int i 0; i n; i) { arr[i] i; } return arr; } }我自己在某次测试中得到的数据仅供参考基础版本固定末尾基准在十万随机数据下耗时约30ms但在十万有序数据下直接栈溢出加入随机化基准之后十万有序数据约12ms百万随机数据约130ms加上三数取中和插入排序切换之后整体还能再提升5%~10%。差距最大的是千万级别的数据量优化前后的差距可以拉大到3倍以上。5.2 工程中的快速排序JDK怎么用Java开发者可能每天都在使用快速排序自己却没有意识到。JDK中java.util.Arrays.sort(int[])底层针对基本类型数组采用的是双轴快速排序Dual-Pivot QuickSort而针对对象数组采用的则是TimSort。双轴快速排序的核心理念是选择两个基准元素一趟遍历把数组切成三段小于基准1、介于基准1和基准2之间、大于基准2。理论上分段越多单趟扫描后问题的规模缩得越快实际测试中它比经典单基准快排在大量数据上能提升约10%~20%。这背后的权衡很微妙段数增加意味着每趟扫描需要处理的条件分支更多但递归深度相应变浅CPU缓存局部性更好。了解这些底层实现的意义在于日常开发中绝大多数排序需求可以直接用Arrays.sort和Collections.sort不需要自己重写。但当你面对的是自定义对象的特殊排序需求、内存极度受限的环境、或者需要理解线上性能问题的成因时底层的算法选择逻辑就显得非常重要了。5.3 一些个人建议在我实际工作里快速排序的出场率远不如网上讨论的那么高——大部分业务排序用现成工具类一行就搞定了。但快速排序本身的价值恰恰体现在“基础”二字上它是理解递归、理解分治、理解复杂度分析最好的教材之一也是面试中考察候选人代码基本功的高频题目。我给准备面试的人一个建议不要满足于“能写通”要能解释partition每一步的含义能说出最坏情况怎么产生、如何规避能对比Lomuto和Hoare的优劣。这些追问才是面试官真正想听的。如果要从这篇内容里带走一个实操点我最想让你记住的是三数取中配合插入排序切换这个组合。它既规避了最坏情况又利用了小数组的高效性是经典快速排序到工程级快速排序之间最值得补上的一课。至于并行化、双轴分区等真正在业务里遇到性能瓶颈时再去研究也不迟。最后说一个细节写完快速排序别忘了跑一遍空数组、单元素数组、全部相同元素的数组、升序数组、降序数组这五个边界用例。这是我用来验证排序实现是否可靠的标准测试集哪怕只是多写几行测试代码的成本也比线上排错便宜太多。