每次面试问到排序算法我都会先反问自己一句我要的是稳定排序、原地排序还是单纯的排序结果这个问题看起来简单却直接决定了算法选型的方向。排序算法是数据结构课程里最基础也最容易被低估的一块内容它不只是几段可以背下来的代码而是理解复杂度分析、递归、分治、堆和二叉树这些核心概念的黄金切入点。这篇文章围绕七大经典排序算法和非比较排序展开用 Java 代码逐行拆解讲清楚每个算法为什么这样写、复杂度是怎么算出来的、稳定性到底影响什么同时结合工程实践和面试高频考点把排序讲透。无论你是正在准备算法面试还是想系统回顾数据结构基础这篇文章都能帮上忙。1. 排序算法全景拆解先用一张表看清七大排序1.1 七大比较排序到底是哪七个常规说法里的七大排序算法指的全都是基于元素之间“比较大小”来决策的排序方法它们分别是冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序。前三个是基础排序平均时间复杂度都在 O(n²) 这个级别代码短、思路直观但数据量一大就不太行了。希尔排序是插入排序的改进版通过分组跳跃式交换把复杂度压到接近 O(n log n)。归并、快排、堆排则是真正意义上的高效排序平均时间复杂度在最坏情况下也都有保证只是各自有各自的空间或稳定性代价。我用下面这张表把这七个算法按时间、空间、稳定性做一个直观的对比后续每部分会针对它们展开细说排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定希尔排序O(n^1.3~1.5)O(n²)O(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定从表里能明显看出没有哪个排序是全能选手。稳定的通常慢快的通常不稳定省内存的往往边界条件脆弱。实际工程里就是在这些维度里做取舍后面会专门讲。1.2 稳定性和原地性这两个概念别搞反学习排序算法之前先把两个基础术语弄清楚稳定性、原地排序。稳定性指的是如果两个元素的值相等排序后它们在数组中的相对顺序是否保持不变。相对顺序不变就叫稳定排序变了就叫不稳定排序。举个例子有一批订单先按下单时间排好序再按金额排序如果排序是稳定的那么相同金额的订单内部依然保持时间顺序如果不稳定金额相同的订单在二次排序后顺序可能被打乱。这个特性在业务排序、动态榜单、多字段排序里非常关键。原地排序指的是排序过程中不需要依赖额外的、与数组规模成正比的存储空间像冒泡、选择、插入、快排、堆排都属于原地排序。归并排序因为需要额外的 O(n) 合并数组严格来说就不是原地排序。这两个维度常常被人混为一谈其实它们完全独立。一个排序可以原地但不稳定比如堆排和选择排序也可以非原地但稳定比如归并排序。工程上对象类型的排序对稳定性要求更高比如 JDK 里的对象排序就采用了稳定排序策略这点我会在第 5 章展开。1.3 为什么建议先手写一遍再背结论面试里被问排序算法时现场打代码考察的不只是记忆而是对边界条件和复杂度是否真的理解。比如快排的递归边界怎么写归并排序临时数组什么时候复制堆排序的下沉循环什么时候终止这些细节写错一个整个排序结果就会不对。我自己带过不少同学发现很多人能说出“快排是 O(n log n)”但让他手写却发现 partition 返回的基准位置根本没对上或者递归出口写成了left right导致死循环。与其背结论不如把每个排序在小规模数组上手动模拟一遍比如用[3, 1, 4, 1, 5, 9, 2, 6]推演过程再对照代码实现。这个练习做下来排序算法的复杂度不是记忆的而是推出来的。2. O(n²) 级别三剑客冒泡、选择、插入的代码与优化2.1 冒泡排序相邻交换的朴素思想与两个优化点冒泡排序的核心思想是每一轮从头到尾比较相邻两个元素如果前一个大于后一个就交换一轮结束后最大值就会像气泡一样沉到数组末尾。用 Java 实现public static void bubbleSort(int[] arr) { int len arr.length; for (int i 0; i len - 1; i) { boolean swapped false; for (int j 0; j len - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); swapped true; } } if (!swapped) { break; } } }内层循环的终止条件是len - 1 - i原因很简单经过 i 轮冒泡后数组末尾的 i 个元素已经是全局最大的 i 个值了不需要重新比较。这段代码里我加了一个swapped标记如果某一轮里没有任何元素交换说明整个数组已经有序可以提前退出这就是冒泡排序最经典的一处优化。在此基础上还可以做双向冒泡也就是“鸡尾酒排序”。它每轮先从前往后冒泡一轮再从后往前冒泡一轮对数据中有少量大元素时确实能减少轮数但整体复杂度规模不变。冒泡排序最大的价值在教学和理解相邻交换的过程实际生产中几乎不会拿它应对大量数据因为即使在理想情况下它也绕不开大量的比较操作。2.2 选择排序交换次数少但稳定性天然劣势选择排序的思路是每轮从待排序区间中找到最小值把它和区间第一个元素交换位置。Java 实现如下public static void selectionSort(int[] arr) { int len arr.length; for (int i 0; i len - 1; i) { int minIndex i; for (int j i 1; j len; j) { if (arr[j] arr[minIndex]) { minIndex j; } } swap(arr, i, minIndex); } }这段代码每轮都能把未排序区间的元素个数减一比较次数始终是n * (n - 1) / 2不会因数据有序而减少所以最好情况和最坏情况一样都是 O(n²)。不过它的交换次数只有 O(n)因为每一轮最多交换一次对于“写交换操作代价极高”的场景比如元素是复杂对象且交换开销大时选择排序的交换次数反而是它相对冒泡的一大优势。但它有一个致命的弱点不稳定。举个直观的例子数组是[3a, 1, 3b]第一轮找到最小值 1把它和 3a 交换结果数组变成[1, 3b, 3a]两个 3 的相对顺序对调了。这种“跨越式交换”是选择排序不稳定的根源只要最小值前面存在与它相邻的相同值秩序就可能被打乱。2.3 插入排序近似有序场景下的隐藏王者插入排序的思想类似于打扑克时理牌把新区间的第一个元素取出来往左扫描已排序区间找到合适的位置插入。它的 Java 实现非常有代表性public static void insertionSort(int[] arr) { for (int i 1; i arr.length; i) { int cur arr[i]; int j i - 1; while (j 0 arr[j] cur) { arr[j 1] arr[j]; j--; } arr[j 1] cur; } }注意这里我没有用频繁的swap而是先把当前元素保存出来然后让比它大的元素逐个后移最后在正确位置直接赋值。这个“搬运”过程比反复交换要快也是工程代码里常见的写法。插入排序的时间复杂度取决于数据初始状态完全有序时每轮只需一次比较整体 O(n)完全逆序时最坏 O(n²)。这个特性让它成为“数据量小”和“近似有序”两种场景下的王者。快速排序等高级算法在递归到子区间很小时往往直接改用插入排序收尾而不是继续递归。JDK 内置排序和很多工业级排序库都在底层这么干因为当区间长度小于某个阈值比如 7 或 16 时插入排序的开销远小于快排的分区开销。三剑客放在一起看冒泡和选择的问题都是“不管数据长什么样比较量都固定”而插入排序能利用数据已有的有序性这也是它能在工程底层活下来的核心原因。3. O(n log n) 梯队希尔、归并、快排、堆排的核心逻辑3.1 希尔排序插入排序的聪明升级版希尔排序的思想可以理解为分组插入排序。它先选一个增量 gap把数组分成若干组每组内分别做插入排序然后逐渐缩小 gap最后 gap 为 1 时整个数组基本有序再做一次完整插入排序。这样做的目的是让元素能以较快速度跨越长距离移动插入排序虽然短距离搬运快但对远距离逆序元素无能为力希尔排序恰恰补上了这一环。public static void shellSort(int[] arr) { int len arr.length; for (int gap len / 2; gap 0; gap / 2) { for (int i gap; i len; i) { int cur arr[i]; int j i - gap; while (j 0 arr[j] cur) { arr[j gap] arr[j]; j - gap; } arr[j gap] cur; } } }gap 的选取会直接影响性能表现。代码里的gap / 2是 Shell 本人提出的简单序列实现容易但最坏仍是 O(n²)。工程上可以用 Hibbard 序列2^k - 1等能把平均复杂度压到 O(n^(3/2)) 甚至更好。希尔排序是不稳定排序因为分组交换会让相等元素的相对位置发生改变。现代工程排序很少直接使用它但“增量”的概念在数据分块问题里经常出现理解它对掌握归并和桶排序也有帮助。3.2 归并排序稳定且稳定地为 O(n log n)归并排序采用的是分治策略把数组从中间一分为二递归排序左半和右半最后把两个有序数组线性合并成一个整体有序数组。合并过程是归并排序的灵魂依赖一个临时数组来完成“双指针归并”。public static void mergeSort(int[] arr, int left, int right) { if (left right) { return; } int mid (left right) 1; 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); }归并排序最好、最坏、平均时间复杂度都是 O(n log n)性能非常稳定。代价是需要额外数组空间复杂度 O(n)。它是稳定排序因为在合并时只要写if (arr[i] arr[j])优先取左半元素相等元素就能保持左半优先级从而保持稳定性。这一点是归并排序对比快排和堆排最大的优势。在工程上归并排序还承担着“外部排序”的重任。所谓外部排序是当数据量大到无法全部放进内存时把大文件切分成多个可以放入内存的小块分别排序后写回磁盘文件最后做多路归并这也是 Hadoop、MapReduce 等大数据框架里 shuffle 阶段排序的底层思路。3.3 快速排序运用最广但最怕“毒药数据”快速排序同样是分治思想区别在于它没有归并那种显式的合并过程。快排先选一个基准值 pivot通过 partition 把数组分成左小右大的两段然后递归处理各自区间。关注点在 partition 环节。最经典的写法是双指针法取区间最右侧元素作为 pivotpublic 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; }这里i始终指向下一个小于等于 pivot 的元素应放置的位置j 遍历区间。遍历结束后把 pivot 换到 i 的位置这样 pivot 左边的元素都小于等于它右边都大于它返回 i 作为新的分界。这个写法简洁但存在一个经典问题如果数组已经有序每次都选到最大或最小值作为 pivotpartition 后左右区间极度不平衡退化成 O(n²)。工程上的对应策略有几个一是随机选基准避免输入数据“恰好”有序二是三数取中比较 left、mid、right 三个位置的值取中间值作为 pivot三是在递归区间足够小时切换到插入排序四是当存在大量重复元素时使用三路快排把数组分成小于、等于、大于三部分这样重复元素不再参与后续递归效率大幅提高。快排的平均时间复杂度是 O(n log n)空间复杂度主要来自递归栈平均 O(log n)最坏 O(n)。它不是稳定排序因为 partition 的交换操作会打乱相等元素的相对顺序。3.4 堆排序原地实现但常数因子偏大堆排序建立在二叉堆的基础上。用数组表示堆时下标i的左孩子是2 * i 1右孩子是2 * i 2最后一个非叶节点下标是len / 2 - 1。排序分两步先建堆再反复把堆顶元素换到数组末尾并重构堆。public static void heapSort(int[] arr) { int len arr.length; for (int i len / 2 - 1; i 0; i--) { siftDown(arr, i, len); } for (int i len - 1; i 0; i--) { swap(arr, 0, i); siftDown(arr, 0, i); } } private static void siftDown(int[] arr, int i, int len) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left len arr[left] arr[largest]) { largest left; } if (right len arr[right] arr[largest]) { largest right; } if (largest ! i) { swap(arr, i, largest); siftDown(arr, largest, len); } }建堆过程从最后一个非叶节点开始自底向上做下沉而不是从根开始向下构建原因是堆的“最大堆”性质必须从局部有序逐步扩散到全局。堆排序的每个操作都能保证时间 O(log n)所以整体最坏时间稳在 O(n log n)。空间上在数组原地操作额外空间 O(1)这是堆排序的最大卖点。但堆排序有不稳定的问题同时因为访问数组的顺序跳来跳去CPU 缓存命中率差工程应用里平均性能通常不如快排。它更适合在一组数据里反复取最大最小值而不是完整排序的场景比如 TopK 问题、优先队列、定时器调度任务等。3.5 这个梯队里怎么选型归并、快排、堆排三者的取舍我总结成一句话追求稳定选归并内存紧张又必须原地排序选堆排平均性能没有特殊要求选快排。实际 JDK 对对象数组排序用归并的改进版 TimSort对基础类型排序用双轴快排因为基础类型排序不需要稳定性追求的是极致的速度。学到这里就可以理解为什么算法面试总爱考察排序通过排一个数组面试官能迅速判断你对递归、分治、堆结构、复杂度和边界条件的掌握程度。这些能力不是背代码能获得的而是靠逐行推导出来的。4. 不比较也能排序计数、基数与桶排序4.1 计数排序用数值范围换时间计数排序基于一个朴素观察如果待排序的整数值只在[0, k]范围内那么我们可以直接统计每个数值出现的次数然后按数值大小依次输出。它不比较元素之间的大小而是利用数组下标天然有序的特性这也是“非比较排序”名称的由来。public static void countingSort(int[] arr, int maxValue) { int[] count new int[maxValue 1]; for (int num : arr) { count[num]; } int index 0; for (int i 0; i maxValue; i) { while (count[i] 0) { arr[index] i; count[i]--; } } }这段代码是最简版的计数排序能排序但不够稳定。如果要求排序后相等元素的相对顺序不变需要再做一个“前缀和反向填充”的操作统计完频次后把 count 数组转成前缀和然后从原数组末尾向前遍历把每个元素放到“前缀和所指示的最终位置”放置成功后把对应前缀和减一。反向遍历的意义在于相等元素会从后往前依次放置恰好保持它们原来的相对顺序。计数排序的复杂度是 O(n k)n 是数组长度k 是数值范围。它有两个致命限制一是数值必须是整数二是 k 不能太大。如果待排序数据只有两个数但取值范围是 0 到一亿开这么大的数组纯属浪费。所以计数排序更适合数据分布密集且范围可预知的场景。4.2 基数排序按位排序的艺术基数排序把整数按位拆分从最低位到最高位逐轮排序。比如对三位数排序先按个位排序再按十位排序最后按百位排序。每一轮使用的排序算法通常就是计数排序因为它稳定且能在 O(n k) 时间内完成按位排序。为什么必须保证每轮排序的稳定性我用一个例子说明先按个位排序后数组内个位数小的在前再看十位时如果十位相同稳定的排序能保持上轮个位排序的顺序。如果使用不稳定排序十位相同的元素之间个位的顺序会乱掉最终结果必然出错。所以基数排序的每一步底层排序都必须是稳定的计数排序这跟比较排序里“稳定性”的概念直接打通了。基数排序的时间复杂度是 O(d * (n k))其中 d 是最大位数。注意它不是全能的如果数字非常大比如 10 亿位数 d 就可能很大性能优势会被稀释。它适合位数有限、数据量大的场景比如身份证号排序、定长电话号码排序、等长字符串字典序排序。4.3 桶排序先分桶再细化桶排序的核心是先根据数据的值域范围把数据均匀划分到若干个桶里各桶内部再用快排或插入排序最后按顺序把桶里的元素合并。它有两个前提一是能提前知道数据的可能取值范围二是数据分布尽量均匀否则大量数据挤进同一个桶桶排序就退化成一般排序。public static void bucketSort(int[] arr, int bucketSize) { int minValue Arrays.stream(arr).min().getAsInt(); int maxValue Arrays.stream(arr).max().getAsInt(); int bucketCount (maxValue - minValue) / bucketSize 1; ListListInteger buckets new ArrayList(bucketCount); for (int i 0; i bucketCount; i) { buckets.add(new ArrayList()); } for (int num : arr) { int bucketIndex (num - minValue) / bucketSize; buckets.get(bucketIndex).add(num); } int index 0; for (ListInteger bucket : buckets) { if (bucket.isEmpty()) { continue; } Collections.sort(bucket); for (int num : bucket) { arr[index] num; } } }桶排序在数据分布均匀时平均时间复杂度可以达到 O(n)但最坏情况下桶内元素严重堆积所有数据都进同一个桶复杂度就会退化到桶内排序本身的复杂度。它和哈希分桶思想很像区别在于哈希是为了快速定位桶排序则利用区间有序性来分而治之。4.4 非比较排序的共同点与使用时机非比较排序共同的前提条件是对待排序数据本身有额外的先验知识值域已知、位数有限、分布均匀。如果输入是一组毫无规律的浮点数且取值范围极大非比较排序往往不适用。因此它们的最佳使用场景是“数据本身结构明显”的专项场景计数排序处理密集小整数基数排序处理长整数或定长字符串桶排序处理均匀分布的浮点数据区间。掌握这些前提条件面试中才不至于做出“对任意数据都套非比较排序”的错误决策。5. 工程实战排序选型、JDK 源码启发与高频面试题5.1 JDK Arrays.sort 是怎么选择排序算法的Java 的Arrays.sort并不是一套代码走天下它针对不同情况做了不同策略。基础类型数组比如int[]、long[]使用 DualPivotQuicksort也就是双轴快速排序。双轴快排选取两个 pivot把区间分成三段相比普通单轴排序减少了比较次数在大量数据上性能非常可观。对象类型数组使用 TimSort它是归并排序的改进版结合了归并和二分插入排序并且能检测输入中已经排好序的区间直接复用它从而在近乎有序的数据上实现接近 O(n) 的速度。为什么对象数组选稳定排序基础类型选不稳定排序核心原因在于业务需求。对象数组往往承载业务属性比如按金额排序、按时间排序、按名称排序多次排序时我们希望保留前一轮的排序结果所以稳定性很重要。基础类型只有值没有“相对顺序”这个概念稳定性没有意义不如直接追求极致性能。我在做实际项目时就用过这个特性一次需要对一个对象列表按两个字段排序正确做法是先按次要字段排序再按主要字段做稳定排序这样主要字段相同的对象之间能保留次要字段的排序结果。这正是 TimSort 稳定特性最直接的工程价值。5.2 TopK 问题堆排序和快排 partition 谁更合适TopK 问题里最经典的场景是求海量数据中最大的 K 个数。一种方案是用容量为 K 的小顶堆建堆后每来一个新元素如果比堆顶大就替换堆顶并下沉调整遍历完所有数据后堆里就是最大的 K 个数时间复杂度 O(n log K)。另一种方案是每次用快排 partition 找到第 K 大的位置根据分区位置淘汰一半数据平均性能接近 O(n)但最坏情况下退化严重。这两个方案没有绝对的答案。堆方案的优点是稳定可控、内存占用小且不需要一次性读入全部数据非常适合流式数据快排 partition 方案在内存充足且数据能整体加载时更快因为它的常数因子非常小。大数据离线统计通常优先考虑堆方案因为它天然支持分批处理。5.3 逆序对计数为什么用归并排序最顺手逆序对问题是求数组中满足i j且arr[i] arr[j]的元素对数量。暴力枚举是 O(n²)但如果借用归并排序的合并过程可以在合并左右两个有序子数组时顺便统计。每当右半区间的元素小于左半区间的剩余元素时说明左半区间从当前下标到 mid 的所有元素都和这个右半元素形成逆序对直接累加mid - i 1即可。通过对排序过程的改造原本的 O(n²) 问题被压到 O(n log n)。private static int mergeAndCount(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; int count 0; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { count mid - i 1; 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); return count; }这种“利用排序过程顺手解决统计问题”的思路很常见类似的还有寻找区间最大差值、统计数组中的重复元素等衍生问题。它要求你对归并过程的每个细节都理解到位尤其是左右指针的移动时机。5.4 外部排序与大数据场景前面提过归并排序是外部排序的基础。假设有一个 10 GB 的日志文件需要按时间排序但内存只有 1 GB此时不能一次性读入全部数据。实际做法是把大文件切成多个不超过内存限制的块每块读入内存用快排排序后写回磁盘形成多个有序临时文件再做多路归并。多路归并不是简单的两两合并而是用优先队列从多个有序文件中轮流取最小值这就是分布式排序引擎的底层模型。这部分工程实现比普通排序复杂得多但底层算法无非就是归并排序的思想。理解这一点以后你会明白为什么排序算法属于基础中的基础它能串起从递归、堆、优先队列到文件 IO 的整个知识链。6. 排序算法调试实录我最常踩的四个坑6.1 递归边界写反导致栈溢出写排排序和快速排序时最容易出现的问题是递归出口写错。归并排序的关键是left right时直接返回因为单个元素或空区间不需要排序。如果把条件写成left right当某个递归调用传入空区间时就会无限递归下去直接栈溢出。快排的递归调用则必须保证 partition 返回的下标不在递归区间内否则也会陷入死循环。我的习惯是在写完后用空数组、单元素数组、两个元素数组三个极简用例先跑一遍栈溢出问题通常立刻就能暴露。6.2 区间开闭问题就差一个等于号排序代码里最常见的边界问题就是区间开闭写错。如果你约定区间是左闭右闭[left, right]那递归时必须确定所有边界都遵守这个约定。比如归并排序中while (i mid)的等号必须写因为 i 从 left 出发mid 是左半区间最后一个元素漏掉等号等于丢失一个元素。快排的 partition 结束后左区间是[left, pivotIndex - 1]右区间是[pivotIndex 1, right]pivot 本身已经就位如果再把它包含进子区间递归就会造成无限递归。写排序之前我建议先在纸上标清楚每个区间的开闭性质再落代码。6.3 堆排序的下标换算错误堆排序里最后一个非叶节点的下标是len / 2 - 1很多人会记成len / 2。为什么是len / 2 - 1因为数组最后一个元素的下标是len - 1它的父节点下标是(len - 1 - 1) / 2也就是len / 2 - 1。如果从len / 2开始就会从一个叶子节点开始下沉虽然是安全的但多做了很多无意义的操作而且容易在堆调整边界上出问题。另外下沉时的递归调用要传入新的 largest 下标不能把旧的 i 带进去。6.4 测试排序别只用随机数组很多人写完排序后只随机生成大数组验证结果这是不够的。我建议每次都用三类数据测试完全有序的数组、完全逆序的数组、包含大量重复元素的数组。第一类能验证插入排序的提前终止逻辑和快排在有序输入下是否退化第二类能验证递归深度是否过深、案例是否可能出现栈溢出第三类能验证快排是否出现严重的分区失衡同时也能检验排序的稳定性。如果写的代码在这三类数据上都能保持逻辑正确和时间可接受才叫真正过关。写排序算法这件事很多人以为背得越快越好实际操作下来我反而觉得慢一点更好。花一晚上把每一轮交换在纸上画出来把每个递归出口的原因想清楚比机械复制十遍代码更有价值。排序算法真正教给我的是一种对复杂度和边界条件的直觉这个直觉在之后学习二叉树、图算法、动态规划时都会持续发挥作用。如果你也想彻底掌握这部分内容我的建议是把这十种排序都自己手动实现一遍再写一个随机测试对比它们的耗时和稳定性那一刻你对排序的理解会完全不同。