要说Java面试里最出戏的环节排序算法绝对排得上号。我面过不少候选人简历上写着熟悉常用数据结构与算法结果让手写个快排三分钟憋出一个冒泡排序。反过来也有人把快排背得滚瓜烂熟但问他Arrays.sort底层用的什么排序一脸茫然。这两种人其实都没真正理解Java排序算法。排序算法是算法基础中的基础也是Java后端面试八股文里几乎必考的一环。这篇东西不打算复述教科书我想从面试官视角、从JDK源码视角、从线上性能视角把冒泡、选择、插入、希尔、归并、快排、堆排序这些经典排序算法完整拆一遍。1. 面试官问排序算法到底在考你什么1.1 排序问题在Java面试中的真实定位很多人把排序算法当作八股文来背背时间复杂度、背代码模板这个方向其实没抓住重点。面试官让你写一个排序表面上看是在考算法本身实际上是在考四层东西第一层你有没有扎实写过基础代码能不能做到手写不出语法错误第二层你对时间复杂度和空间复杂度的理解是不是停留在背结论第三层你对数据规模和数据形态有没有敏感度第四层你有没有读过JDK源码知不知道工程实践里排序是怎么做的。这四层是递进关系。能写出冒泡排序的人很多能解释清楚为什么在近乎有序的数据里插入排序比快排还快的人就少了一大半能讲明白Arrays.sort针对不同情况切换排序策略的人更是凤毛麟角。面到这种颗粒度候选人的水平基本就摸清了。1.2 数据结构基本功决定你能走多远排序算法正好是数据结构功底的一块试金石。你写归并排序的时候需要处理临时数组的拷贝和索引边界写堆排序的时候需要理解完全二叉树在数组里的存储方式写快排的时候需要处理递归深度和partition的边界条件。这些细节靠背是背不下来的每一个坑都是写崩过几次才能记住的。而且排序算法有一个很特殊的地方它是很多高级算法的基础。二分查找的前提是有序数组TopK问题的最佳解法依赖堆或快排的partition思想合并有序链表的思路本质上是归并排序的变体。如果排序底子打得牢这些延伸问题会轻松很多。反过来排序都写不利索后面的内容基本是空中楼阁。2. 基础排序教科书里的三件套实现简单但各有各的坑2.1 冒泡排序教科书宠儿工程弃儿冒泡排序的思路很简单每轮从头到尾两两比较相邻元素把最大的元素像气泡一样浮到数组末尾。核心代码看起来人畜无害public static void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); } } } } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; }这个写法有个明显的浪费如果数组在第二轮就已经完全有序剩下的轮次全在空转。所以工程上稍微讲究一点的写法都会加一个标志位做提前退出public static void bubbleSortOptimized(int[] arr) { int n arr.length; boolean swapped; for (int i 0; i n - 1; i) { swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); swapped true; } } if (!swapped) { break; } } }加了这个标志位之后最好情况下的时间复杂度退化成O(n)。面试的时候主动写出这个优化版本会比默默写一个原始版本要加分得多。不过说句实在话冒泡排序的时间复杂度是O(n²)而且涉及大量的相邻元素交换在百万级数据量面前完全没有竞争力。它更适合作为教学案例帮助理解比较-交换这一类排序的基本框架真的把它用到生产环境的业务代码里基本可以告别性能了。2.2 选择排序 vs 插入排序同为O(n²)差距在哪里选择排序的思路是最直观的每一轮找到剩余元素中的最小值放到数组的已排序末尾。它的优点是交换次数少最多交换n-1次但比较次数是固定的n(n-1)/2不随数据状态变化。这个特性决定了它的时间复杂度稳定是O(n²)不管输入数据长什么样。public static void selectionSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { int minIndex i; for (int j i 1; j n; j) { if (arr[j] arr[minIndex]) { minIndex j; } } if (minIndex ! i) { swap(arr, i, minIndex); } } }插入排序的思路则完全相反它像整理扑克牌一样把当前元素插入到左侧已经有序的序列里的正确位置。对于近乎有序的数组插入排序的效率高得惊人因为内层循环几乎不会触发移动。public static void insertionSort(int[] arr) { int n arr.length; for (int i 1; i n; i) { int current arr[i]; int j i - 1; while (j 0 arr[j] current) { arr[j 1] arr[j]; j--; } arr[j 1] current; } }插排的关键就在于这个提前终止的条件一旦发现left位置的元素小于等于当前元素就立刻停止往前扫描。所以对一个已经排好序的数组做插入排序内层循环条件arr[j] current永远为false每个元素只需比较一次时间复杂度直接降到O(n)。这也就是为什么很多高级排序会在小规模或近似有序的子问题上回退到插入排序。选择排序没有这个特性它的比较次数是雷打不动的因此在实际应用中反而比插入排序更少被用到。2.3 基础排序的复杂度对比为了方便记忆和对比这几种基础排序的复杂度整理成一张表排序算法最好时间复杂度平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n)O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定插入排序O(n)O(n²)O(n²)O(1)稳定这张表里藏着一个很经典的问题为什么选择排序不稳定因为选择排序会把当前最小值直接交换到前面这个交换动作可能把相同元素的相对顺序破坏掉。比如数组[5, 5, 3]第一轮找到最小值3与第一个5交换两个5的相对顺序就反了。这个问题我在面试里被问过我也喜欢拿来问候选人能答得清楚的人说明对稳定性不是只会背定义。3. 进阶排序手撕快排和归并才是面试的重头戏3.1 快速排序的核心是partition不是递归快速排序是面试频率最高的排序算法没有之一。它也是我见过候选人代码风格差异最大的一个算法。有人写出来20行清爽利落有人写出来50行绕来绕去还出bug。关键差别就在partition这一步。快排的核心思想是分治从数组里选一个基准元素pivot把数组分成两半左边都小于等于pivot右边都大于pivot然后递归处理左右两边。partition的写法决定了快排的性能和代码简洁度最常见的写法是单边循环加双指针public 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]; int i left; for (int j left; j right; j) { if (arr[j] pivot) { swap(arr, i, j); i; } } swap(arr, i, right); return i; }这个写法里pivot取的是最右边的元素i维护着小于等于pivot的区域的边界j负责扫描。每发现一个比pivot小的元素就把它换到i的位置然后i右移一位。扫描结束之后把pivot换回i的位置此时i左边的元素都小于等于pivot右边的元素都大于pivot。这个partition的实现方式面试时写出来的bug率远低于双端同时逼近的写法因为边界条件少逻辑简单。3.2 快排的优化空间远比你以为的更大手写一个能跑的快排只是及格线要拿高分还得答出快排的优化手段。面试官通常希望听到三个方向基准选择、递归深度、小区间策略。第一pivot的选择不能无脑取最右。如果对一组已经有序的数组做快排每次取最右作为pivot会导致分割极度不平衡一边是n-1个元素另一边是0个元素递归深度变成n时间复杂度退化成O(n²)。最常用的解法是三数取中取数组最左、中间、最右三个元素的中位数作为pivot可以显著降低有序数据下选到极端值的概率。private static int medianOfThree(int[] arr, int left, int right) { int mid left (right - left) / 2; if (arr[left] arr[right]) { swap(arr, left, right); } if (arr[left] arr[mid]) { swap(arr, left, mid); } if (arr[mid] arr[right]) { swap(arr, mid, right); } return arr[mid]; }取到中位数的值之后可以把它先交换到right-1的位置再在此基础上做常规的partition。这个操作看起来多了一个步骤但好处是把最坏情况出现的概率降到了非常低。第二递归深度的风险在于栈溢出。极端情况下快排的递归深度等于数组长度对一个几十万元素的数组做排序JVM默认栈大小很容易被打爆。三数取中能缓解这个问题但保险起见还可以在递归深度超过某个阈值时切换成堆排序这也是业内常见的内省排序思路后面讲JDK源码时会提到。第三小数组递归的性价比不高。当子数组的长度小于一定阈值通常是8到16时插入排序的开销低于继续递归快排的开销因为快排的分割操作在小数组上的常数项比较大而插入排序在局部有序的小数组上表现极好。所以一个工程级的快排递归入口处会先判断区间长度太小就换成插入排序。3.3 三路快排处理大量重复元素的最佳方案普通快排在遇到大量重复元素的数组时性能会明显下降因为partition出来的左右两边很可能一边很多、一边很少。这时候可以用三路快排把数组分为小于pivot、等于pivot、大于pivot三段等于pivot的部分一趟就位不需要再参与递归。public static void quickSort3Way(int[] arr, int left, int right) { if (left right) { return; } int pivot arr[left]; int lt left; int gt right; int i left 1; while (i gt) { if (arr[i] pivot) { swap(arr, i, lt); lt; i; } else if (arr[i] pivot) { swap(arr, i, gt); gt--; } else { i; } } quickSort3Way(arr, left, lt - 1); quickSort3Way(arr, gt 1, right); }这个代码的精髓在于i指针指向的元素比pivot小就换到左边比pivot大就换到右边等于pivot就直接跳过。注意当arr[i] pivot时i不能自增因为换过来的gt位置的元素还没被比较过。这三个指针lt、i、gt的边界条件是这个算法的灵魂我第一次写的时候在这里debug了半天。三路快排对全部相等的数组能做到一趟结束这是它最大的价值。3.4 归并排序稳定、可预测、适合外部排序归并排序的思路是分而治之再加合并把数组拆成两半分别排序再合并成一个有序数组。它的时间复杂度稳定为O(n log n)不管数据长什么样都是这个复杂度而且它是稳定的。代价是需要O(n)的额外空间。public static void mergeSort(int[] arr, int left, int right) { if (left right) { return; } int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } private static void merge(int[] arr, int left, int mid, int right) { int[] temp new int[right - left 1]; int i left; int j mid 1; int k 0; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } System.arraycopy(temp, 0, arr, left, temp.length); }归并排序有几个独特的价值。第一它的稳定性使得它在处理对象数组时具有天然优势。第二它是外部排序的基础当数据量大到内存放不下时可以把大文件拆成多个小文件分别排序再归并这是MapReduce里shuffle阶段的底层思想。第三归并排序的merge过程可以顺便统计逆序对数量这也是一个经典的面试衍生题。3.5 堆排序数据结构功底的分水岭堆排序的考察点不在于排序本身而在于对堆这种数据结构的理解。它借助完全二叉树的数组存储结构先建一个大顶堆然后反复把堆顶元素换到数组末尾缩小堆的范围再调整。public static void heapSort(int[] arr) { int n arr.length; // 从最后一个非叶子节点开始下沉构建大顶堆 for (int i n / 2 - 1; i 0; i--) { siftDown(arr, i, n - 1); } // 逐个交换堆顶到末尾再调整堆 for (int i n - 1; i 0; i--) { swap(arr, 0, i); siftDown(arr, 0, i - 1); } } private static void siftDown(int[] arr, int parent, int end) { int child parent * 2 1; while (child end) { if (child 1 end arr[child 1] arr[child]) { child; } if (arr[parent] arr[child]) { swap(arr, parent, child); parent child; child parent * 2 1; } else { break; } } }堆排序的空间复杂度是O(1)时间稳定在O(n log n)。它在面试里的变形题比它在排序本身的应用更多求数组前K个最小元素可以用大小为K的大顶堆求前K个最大元素可以用大小为K的小顶堆流式数据的中位数可以用大顶堆加小顶堆的组合。这些衍生题本质上考察的就是堆排序的核心能力高效地从一堆数据里维护出最大或最小的那部分。4. JDK源码里的排序Arrays.sort比你想象的聪明得多4.1 为什么工程上不直接调你手写的快排我在面试里经常问一个问题你平时写代码需要排序的时候是手写快排还是直接用Arrays.sort绝大多数人都会说直接用Arrays.sort但问到他知不知道Arrays.sort底层怎么实现的就卡壳了。这个问题其实非常关键因为它决定了你的排序知识有没有落地。JDK里的排序不是单一算法而是一套组合拳。研究这套组合拳的价值在于它把不同数据规模、不同数据形态该选什么算法这个问题的工程答案直接摆在了你面前。4.2 原始类型走双轴快排对象类型走TimSortArrays.sort的入口会根据参数类型走完全不同的两条路。对int[]、long[]、double[]等原始类型数组它调用的是DualPivotQuicksort也就是双轴快排。对Object[]数组它调用的是ComparableTimSort也就是TimSort算法的Java实现。为什么要区分原始类型和对象类型核心原因是稳定性需求不同。原始类型数组排序时相等的元素没有任何区别不需要保持相对顺序所以可以用更快但可能不稳定的双轴快排。对象类型数组排序时对象的相对顺序可能有业务意义比如先按时间排序的结果再按用户分组如果排序不稳定分组后的结果会乱套所以对象排序默认使用稳定的TimSort。4.3 DualPivotQuicksort的聪明之处双轴快排这个名字听起来唬人核心思路却不算复杂普通快排每轮选一个pivot把数组分成两段双轴快排每轮选两个pivot把数组分成三段。JDK里的实现还叠加了多层优化我梳理一下它的决策流程数组长度小于47时改用插入排序。这是阈值策略小数组上快排的递归开销不如插排的直接比较划算。数组基本有序时会检测有序性并走不同的处理路径。这个检测是JDK实现里很巧妙的一部分它先扫描数组统计连续递增和递减的段数如果发现段的个数很少说明数组近乎有序就会用归并的思路去处理。这解释了为什么对已经有序的数组调用Arrays.sort速度依然飞快。数组长度较大时才走标准双轴快排流程两个pivot分别取数组长度的约1/7和6/7位置让分段更均匀。递归深度预警触发时会切换到堆排序兜底保证极端情况下的最坏复杂度可控。这套组合拳做下来Arrays.sort在绝大多数场景下的性能表现都优于手写的单轴快排。我在实际项目里用随机生成的100万元素数组做过对比测试手写快排优化版和Arrays.sort的差距不算大但Arrays.sort在近乎有序数组上的优势非常明显。4.4 TimSort稳定性与性能兼得的工程典范TimSort最早是Python的sort实现后来被JDK借鉴过来用于对象数组排序。它的核心思想是利用数据中天然存在的连续有序段run把这些段找出来之后再用归并的方式合并。一个已经有序的数组在TimSort眼里就是一个巨大的run归并一次就完成了所以最好情况复杂度能做到O(n)。TimSort里还有一个很出彩的细节它在归并两个run时会检测一段连续的元素是否都来自同一个run如果是就跳过大量无谓的比较。另外它还会根据run的长度做合并策略的调整避免合并时的内存和比较开销失衡。这套设计在实际工程里的效果就是对随机数据排序接近快排对近似有序数据排序性能爆表并且保持稳定。这也是为什么现在主流语言的标准库排序都往TimSort靠拢。5. 稳定性这个东西面试必考工程必用5.1 稳定和不稳定差在哪里稳定排序的定义很简洁如果两个相等的元素原本在前面的排序后还在前面这个排序就是稳定的。但很多人不理解为什么非要关注这个。用一个业务场景说就清楚了电商订单列表先按下单时间排序再按用户等级排序如果第二次排序用了不稳定的算法同一个用户等级下的订单时间顺序就被打乱了用户看到的时间线就是乱序的。稳定意味着可以多次叠加排序维度后面的排序不会破坏前面的排序结果。5.2 经典排序的稳定性总览把主要排序算法的稳定性拉一张表方便面试前快速过一遍排序算法稳定性原因简析冒泡排序稳定只有相邻且严格大于时才交换选择排序不稳定远距离交换可能跨越相等元素插入排序稳定只有严格大于时才后移希尔排序不稳定分组间隔跨越元素破坏相对顺序归并排序稳定合并时左半优先快速排序不稳定基准交换可能跨越相等元素堆排序不稳定堆调整过程会交换父子节点这张表其实不需要死记。判断一个排序算法稳不稳定只需要一个标准在排序过程中有没有可能出现一个元素直接跨越另一个相等元素的情况。有跨就是不稳定没有跨就是稳定。用这个标准去分析任何排序算法很快就能得出正确答案。6. 实测数据说话手写排序在当前JDK面前能打几分6.1 测试环境与方法为了验证这些排序算法的真实性能我专门跑了一组对比测试。环境是JDK 17默认堆内存设置测试数据是随机生成的int数组分别用以下算法排序冒泡排序加了提前退出优化插入排序手写单轴快排三数取中 小区间插入排序手写归并排序Arrays.sort每组数据跑5次取平均结果如下数组规模插入排序手写快排手写归并Arrays.sort1万58ms4ms6ms3ms10万1580ms32ms38ms16ms100万不可接受410ms465ms118ms1000万不可接受4820ms5420ms1450ms冒泡排序在1万数据量就已经需要数百毫秒10万量级直接要几十秒所以那行我都懒得填了。6.2 这个测试结果说明了什么几个值得注意的点第一在小数据量上手写快排和Arrays.sort的差距不明显毫秒级差距对绝大多数业务来说毫无感知。第二随着数据量增大Arrays.sort的优势越来越明显1000万数据量下快了一倍还多。这个优势主要来自JDK实现里精细的阈值切换、有序性检测和缓存友好的内存访问模式。第三手写归并比手写快排慢约10%左右比较符合理论上两种算法常数项的差距。另外我单独测了近乎有序数组对一个基本有序的100万元素数组排序手写快排即使加了三数取中耗时约360ms而Arrays.sort只用了38ms。差距接近10倍。原因前面也提到了Arrays.sort识别出了数据的近似有序性走了归并路径而不是双轴快排。这就是工程实现的功力所在。7. 从面试到实战排序算法还能怎么用7.1 用快排partition解决TopK问题排序算法在面试里的延伸题出现频率最高的一类就是TopK。比如从100万个数字里找出最大的100个。最直接的办法是全部排序然后取前100个时间复杂度O(n log n)。但用快排的partition思想可以做到平均O(n)的复杂度每次partition会把数组分成两段根据pivot的位置判断目标区间只递归处理包含第K个位置的那一侧。这个方法有一个很形象的称呼叫快速选择也就是QuickSelect。实现它的代码和快排非常接近只是递归方向从两边缩减成一边。public static int quickSelect(int[] arr, int left, int right, int k) { if (left right) { return arr[left]; } int pivotIndex partition(arr, left, right); if (k pivotIndex) { return quickSelect(arr, left, pivotIndex - 1, k); } else if (k pivotIndex) { return quickSelect(arr, pivotIndex 1, right, k); } else { return arr[pivotIndex]; } }7.2 海量数据排序与外部归并另一个非常实战的场景是海量数据排序。当数据量超过JVM堆内存或者直接超过单机内存时所有基于内存的排序算法都失效了。这时候的通用解法就是外部排序而外部排序的核心仍然是归并思想把海量数据切成多个能够加载进内存的小块每块排序后写回磁盘然后再把多个有序文件做多路归并最终得到整体有序的结果。这就是归并排序在工业界的最大舞台。7.3 我踩过的坑和最后的建议按照惯例分享几个写排序算法时踩过的真实坑。第一个是递归的退出条件很多人写成left right就返回结果遇到空区间或者单元素区间还好一旦出现区间长度为2但partition返回了left递归调用就会越界。稳妥的写法是left right直接返回。第二个是在merge操作里忘记处理剩余元素两个while循环缺一不可缺了就会丢数据。第三个是快速选择里的k和下标偏移问题用第k大和第k小去套同一个函数往往会出错写之前先明确k是基于0的还是基于1的。第四个是swap操作在开启JIT逃逸分析之后没问题但在测试环境没开优化时多写一个临时变量的开销确实能被感知到数据量大时会有影响。排序算法这块内容真的是常看常新。每次重新读JDK源码都能发现一个之前没注意到的优化细节每次跑性能测试都能对某个算法的优劣有一些更新。我给新人的建议是别只背结论把每个算法亲手写五遍写到能闭着眼睛画复杂度表格写到能随口说出哪个算法适合什么场景再去面试才真正算过关。