Java排序算法全解析：从面试八股到JDK源码与工程实践

要说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 基础排序的复杂度对比

为了方便记忆和对比，这几种基础排序的复杂度整理成一张表：

这张表里藏着一个很经典的问题：为什么选择排序不稳定？因为选择排序会把当前最小值直接交换到前面，这个交换动作可能把相同元素的相对顺序破坏掉。比如数组[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 原始类型走双轴快排，对象类型走TimSort

Arrays.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次取平均，结果如下：

冒泡排序在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源码都能发现一个之前没注意到的优化细节，每次跑性能测试都能对某个算法的优劣有一些更新。我给新人的建议是：别只背结论，把每个算法亲手写五遍，写到能闭着眼睛画复杂度表格，写到能随口说出哪个算法适合什么场景，再去面试，才真正算过关。