排序算法这五件套说穿了就是算法面试的“基本功试金石”。不管你是刚刷LeetCode的新手还是准备跳槽的老兵冒泡、选择、插入、快排、计数这五种排序几乎绕不开。有人觉得它们太基础、没含金量但说实话能把它们的原理、适用场景和代码细节讲清楚本身就是一种能力的体现。尤其是快速排序和计数排序一个代表了分治思想在工程上的极致发挥一个代表了“用空间换时间”的另类思路这两者在LeetCode上直接或间接考察的频率相当高。这篇文章我想换个角度聊不打算只贴一遍代码然后扔个复杂度表。我会把每种排序的核心逻辑、为什么这样设计、在LeetCode上哪些题会用到它们、以及我自己踩过的坑和调试心得全部梳理一遍。无论你是刚开始接触还是想体系化回顾一下这篇内容应该都能让你有点收获。1. 内容整体设计与思路拆解我先说下我对排序算法这套内容的理解。很多人刷LeetCode可能习惯直接用库函数Arrays.sort()或者sort()一把梭但排序算法的学习价值绝对不只是“把数组排好序”这么简单。它背后其实是几种完全不同的思维范式冒泡排序和选择排序属于“暴力直观”型每轮迭代确定一个最终位置思路简单直接但效率偏低。插入排序属于“局部有序逐步扩张”型牌局中的整理手牌是它最好的朋友。快速排序属于“分治递归”型核心在于partition分区操作这也是很多题目解题的关键所在。计数排序属于“非比较型”排序完全脱离“两两比较大小”的框架利用数组下标直接定位元素在线性时间复杂度下就能完成排序。我在设计这篇文章的篇幅结构时刻意把快速排序和计数排序安排得比前三种更细。原因很简单冒泡、选择、插入这三种实际工程或面试里很少要求手写更多是要求你“知道并理解它们的代价”而快排和计数排序则是LeetCode题目和面试手撕中正儿八经的常客。尤其是快排它牵扯到递归思想、边界处理、主元选择一不留神就是一堆bug。还有一个思路想先说明白很多初学者容易陷入一个误区就是把五种排序当成五个孤立的“题”来背。但更高效的学习方式应该是抓住每种排序的“不变量”invariant。所谓不变量就是每一轮操作之后数组必然保持的某种性质。比如冒泡排序的不变量是“每一轮结束后末尾至少有一个元素是最终位置上的正确元素”选择排序的不变量是“前缀区间已经全局有序且不会改变”。理解了不变量你就能理解为什么这些算法是对的、为什么它们的复杂度是这个样子也更容易在写代码时定位逻辑错误。2. 五种排序逐个拆解与细节实现2.1 冒泡排序最直观的双重循环冒泡排序的思想一句话就能说清每次比较相邻两个元素如果顺序错误就交换经过一轮最大的元素就“冒泡”到了数组末尾。下一轮再对前面未排序的部分做同样的操作直到全部有序。它的不变量是经过第 k 轮外循环数组最后 k 个元素一定是全局最大的 k 个元素且它们已经处于最终正确的位置。基础代码如下Java版本面试手写最常用public void bubbleSort(int[] nums) { int n nums.length; for (int i 0; i n - 1; i) { // 每一轮都会把当前未排序部分的最大值移动到末尾 for (int j 0; j n - 1 - i; j) { if (nums[j] nums[j 1]) { int tmp nums[j]; nums[j] nums[j 1]; nums[j 1] tmp; } } } }这段代码有几点值得注意第一内层循环的终止条件是n - 1 - i不是固定的n - 1。因为每一轮外层循环结束后已排好的尾部元素不需要再参与比较。第二这里用的是而不是保证了排序稳定性。如果题目要求“相同元素保持原有相对顺序”这个细节就非常关键。虽然LeetCode多数题目不直接考稳定性但你要是面试时能主动提一句“用不稳定的交换方式会破坏稳定性”会是个加分点。第三这种基础写法在数组“基本有序”时效率依然不高。优化方案是加一个boolean swapped标记如果某一轮内层循环没有任何交换说明序列已经完全有序直接break跳出外层循环。public void bubbleSortOpt(int[] nums) { int n nums.length; for (int i 0; i n - 1; i) { boolean swapped false; for (int j 0; j n - 1 - i; j) { if (nums[j] nums[j 1]) { int tmp nums[j]; nums[j] nums[j 1]; nums[j 1] tmp; swapped true; } } if (!swapped) break; } }这个优化在最好情况下数组已经有序能把时间复杂度降到 O(n)只扫描一遍完成检测。这个点可以用来在面试中展示你对复杂度的理解和优化意识。但是实话实说冒泡排序除了教学意义和“几乎有序的小数组”场景实战里很少直接用。它的移动次数太多每次交换都是数组元素的读写操作常数因子偏大。LeetCode上也不会直接让你写个冒泡排序来解决问题但“相邻比较交换”的思路在一些题里依然有影子比如“求逆序对数量”这道题暴力O(n^2)的做法就是冒泡排序的比较逻辑而更优解法就到归并排序了。2.2 选择排序每轮选最小的放前面选择排序的思路更“抠门”每一轮都在未排序区间里找到最小元素把它放到未排序区间的开头。经过 n-1 轮所有元素就位。它的不变量是前 i 个元素已经全局有序并且它们永远不会再变动。public void selectionSort(int[] nums) { int n nums.length; for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (nums[j] nums[minIdx]) { minIdx j; } } if (minIdx ! i) { int tmp nums[i]; nums[i] nums[minIdx]; nums[minIdx] tmp; } } }选择排序有一个比冒泡排序“省”的地方它每轮最多只做一次交换而冒泡排序每轮可能做多次。所以虽然两者时间复杂度同为 O(n^2)选择排序在交换开销上更划算。不过选择排序有一个比较隐蔽的问题它是不稳定的。举个例子数组[5, 5, 1]第一轮选出最小元素1放到开头和第一个5交换这时两个5的相对顺序就被改变了。这个问题在面试中经常被问到“插入排序和选择排序谁稳定”答案永远是插入排序稳定。顺便说一句选择排序在实际做题中出现的频率更低。它最大的价值在于一个很常见的变种“部分排序”。LeetCode上有一类题目比如“数组中的第K个最大元素”如果你用选择排序的思路只需要执行 K 轮外层循环就能在 O(Kn) 时间内找到第 K 大元素。当 K 很小比如 K1 或 K2时这个做法比整体排序还快。2.3 插入排序像打扑克牌一样整理插入排序是我个人最喜欢向新手推荐理解的排序它模拟的是你打扑克牌时把新摸到的牌插入到手中已经有序的牌中。每次插入之后手里的牌依然是有序的。它的不变量是循环变量 i 之前的所有元素已经按序排列每次把第 i 个元素插入到前 i 个元素的正确位置上前缀有序区间长度加一。public void insertionSort(int[] nums) { int n nums.length; for (int i 1; i n; i) { int cur nums[i]; int j i - 1; while (j 0 nums[j] cur) { nums[j 1] nums[j]; j--; } nums[j 1] cur; } }这段代码要特别注意两点第一用一个变量cur暂存当前要插入的元素避免被后面的移位覆盖。很多新手在这里写错直接用nums[j] nums[j1]结果当前元素的值就被丢掉了。第二内层循环从 j i-1 开始向前扫描只要前一个元素大于cur就把前一个元素向右移动一位。这个“移动”代替了“交换”是插入排序效率高于冒泡和选择的关键所在——它在元素比较密集的数组上减少了很多不必要的赋值操作。插入排序还有一个非常经典的优化点在数据量小且基本有序时它的实际性能甚至能超越很多 O(n log n) 的排序。这也是为什么很多高级排序算法包括Java的Arrays.sort()对某些数据类型的实现在递归切割到比较小的子数组时会改用插入排序作为“收尾”。这个思想叫“阈值切换”是工程实践中真实存在的优化策略。在LeetCode上插入排序的思路最直接的应用是“对链表进行插入排序”这道题。链表不像数组可以随机访问需要从头查找插入位置写起来麻烦不少。但如果你理解了数组版本的插入排序再迁移到链表思路其实是顺理成章的还是从第二个节点开始逐个将其插入到已经排好序的链表前缀中。2.4 快速排序分治思想的明星选手快排应该是我在面试中手写频率最高、也见过最多人翻车的排序了。它的核心就一句话选一个主元pivot把数组分成两个部分左边的数都小于等于主元右边的数都大于等于主元然后递归处理两部分。这个“分成两个部分”的过程叫 partition分区。快排的所有细节和坑几乎都藏在这个partition里。我这里推荐一个我自己最常用、也最不容易写错的写法Hoare分区思想的简化版也就是“挖坑法”或“左右指针法”。以取最左元素为主元为例public void quickSort(int[] nums, int left, int right) { if (left right) return; int pivotIndex partition(nums, left, right); quickSort(nums, left, pivotIndex - 1); quickSort(nums, pivotIndex 1, right); } public int partition(int[] nums, int left, int right) { int pivot nums[left]; int i left, j right; while (i j) { while (i j nums[j] pivot) j--; nums[i] nums[j]; while (i j nums[i] pivot) i; nums[j] nums[i]; } nums[i] pivot; return i; }这个写法我强烈建议你背熟并理解每行代码的含义把最左元素nums[left]作为主元值保存下来这时候left位置就“空”了可以看成是一个坑。右指针j向左移动找到第一个小于主元的值把它填入左边的坑这时j位置就变成新坑。左指针i向右移动找到第一个大于主元的值填入j位置的坑。循环直到i和j相遇这个位置就是主元的最终位置直接把pivot填进去。这段代码有个很容易踩的坑内层两个while必须加上i j的条件否则指针会越界或者越过对方。另外如果写法里把都换成和会遇到一些极端样例下的死循环问题比如所有元素相等时指针可能一直不移动。所以边界条件的处理非常敏感。快排的平均时间复杂度是 O(n log n)最坏是 O(n^2)。最坏情况发生在每次选的主元刚好是当前区间最小或最大值时比如数组本身已经有序而你固定选择最左元素作为主元。经典优化方案有两种随机主元在left到right之间随机选一个位置先和nums[left]交换再执行partition。这样最坏情况出现的概率极低。三数取中取nums[left]、nums[mid]、nums[right]三者中的中位数作为主元能有效应对大部分“近乎有序”的输入。LeetCode上快速排序思想的直接应用至少有以下几类第一类是“数组中的第K个最大元素”。这道题的最优解不是先排序再取下标而是“快速选择”QuickSelect每次partition后看主元最后的位置和K的关系只递归处理包含目标的那一侧平均复杂度 O(n)。这个思路我在面试中反复使用代码量不大但边界很绕人。第二类是“颜色分类”俗称荷兰国旗问题。它本质上是“三向切分快排”的一趟partition把0、1、2三类元素分别放到数组的左、中、右三个区域。这个思想在原版快排里进一步发展成了三向切分快排专门用来处理有大量重复元素的数组。第三类是“排序链表”这类要求 O(n log n) 时间且常数额外空间的题目通常大家写归并排序但理解了快排的链表版本你也能换种解法。2.5 计数排序脱离比较的线性时间排序计数排序和前四种完全不是一个维度的东西。它不通过“比较两个元素大小”来决定顺序而是利用元素值的范围创建一个辅助数组用下标记录每个值出现的次数然后按顺序回填。适用条件是数据取值范围比较小且数据规模不小。比如给一个长度为十万的数组每个元素都在0到100之间计数排序可以在O(n)时间内完成排序比任何比较型排序都快。public void countingSort(int[] nums) { if (nums null || nums.length 1) return; int max nums[0], min nums[0]; for (int num : nums) { max Math.max(max, num); min Math.min(min, num); } int range max - min 1; int[] count new int[range]; for (int num : nums) { count[num - min]; } int index 0; for (int i 0; i range; i) { while (count[i] 0) { nums[index] i min; count[i]--; } } }这里有几个细节我想展开说说第一为什么要统计max和min因为并不是所有数据都是从0开始的连续整数。比如[100, 101, 102]这样的数组你如果直接开max1长度的数组会有大量空间浪费。用max - min 1作为辅助数组长度通过num - min做偏移映射既节省空间又保持逻辑清晰。第二计数排序是稳定排序吗上面这个“统计后回填”的简单版本稳定性其实是被打破的。如果要求稳定需要在回填时使用“前缀和”的方式倒序遍历原数组。LeetCode上有一道经典的“按身高排序”或者“按频率排序”的题目如果数据范围有限且需要保持稳定就要注意这个问题。第三计数排序在实际题目中最典型的一个变种是“最小绝对差”、“出现次数最多的元素”这类题它们不一定直接要求排序但在数据范围已知的情况下用计数数组比排序更高效。比如“哪个数字出现的次数最多”你完全可以统计完直接扫一遍计数数组而不需要先排序再遍历。3. 复杂度分析与场景选择我见过不少人背了一堆复杂度但问到“给你一个实际场景你会选择哪种排序”的时候就沉默了。这里我整理了一个表格方便读者对比记忆排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性适用场景冒泡排序O(n^2)O(n^2)O(1)稳定教学演示、几乎有序的小数组选择排序O(n^2)O(n^2)O(1)不稳定数据量小、手写简单插入排序O(n^2)O(n^2)O(1)稳定小规模数据、基本有序、链表排序快速排序O(n log n)O(n^2)O(log n)不稳定通用大规模数组排序、快速选择计数排序O(n k)O(n k)O(k)可稳定可不稳定数据范围小且集中的非负整数这里面有几个概念新手容易混我再强调一下“稳定性”到底什么意思就是排序前如果两个元素相等排序后它们的相对顺序有没有被改变。如果没变就是稳定的。这个属性在实际场景中的价值在于如果你先按A字段排了一次序再按B字段排一次序稳定排序可以保证第二次排序后B相同的元素之间依然保持第一次排序后的A顺序。“常数空间”和“对数空间”的区别冒泡、选择、插入都是原地排序常数额外空间 O(1)。快排虽然也是原地排序但递归调用栈在平均情况下深度是 O(log n)所以空间复杂度是 O(log n)最坏是 O(n)。这个细节面试经常被追问。计数排序的“O(n k)”里这个k是数据范围大小不是数组长度。如果 k 远大于 n比如给一个长度10的数组元素是1到10亿之间的随机数计数排序反而不如快排。选型的经验我总结成三句话第一数据规模小比如小于50别管什么复杂度直接插入排序或者库函数简单可靠。 第二数据规模大元素值是普通整数或对象直接用基于比较的 O(n log n) 排序工程上优先库函数手写选快排。 第三数据规模大且取值范围有限注意取值范围不是数据个数比如年龄、分数、IP地址段的一部分计数排序能带来数量级的性能提升。4. 实际刷题中的问题排查与经验技巧刷LeetCode排序相关题目最痛苦的事情往往不是“不会思路”而是“写了半天样例过了一提交就各种边界报错”。我总结了几类高频踩坑点希望对大家有帮助。4.1 快排边界错误这是我见过最多的一类错误。常见症状包括数组越界、递归栈溢出、死循环、排序结果不对但个别样例又通过。越界问题通常出在partition的两个内层while上。我推荐一个“保命”习惯所有指针移动条件里都加上i j不管你觉得会不会越界先加上再说。哪怕冗余也能避免大多数越界问题。死循环有个非常典型的触发场景数组所有元素都相等。此时如果内层while用的是nums[j] pivot而不是nums[j] pivot左右指针会因为找不到“严格大于”或“严格小于”的元素而卡住。所以在相等元素较多的场景下用和让指针可以跨过相等元素是更安全的做法。三向切分把等于主元的元素单独放中间则能同时解决重复元素导致的性能退化问题。递归栈溢出通常是因为最坏情况的递归深度达到了O(n)。这时候优先考虑换随机主元或者直接改用迭代模拟栈的方式实现快排。后者在LeetCode上算是进阶解法面试时如果主动写出来面试官往往会眼前一亮。4.2 计数排序偏移错误如果你直接按照“值作为下标”去开数组遇到负数和很大的数就会直接越界或者爆内存。解决办法就是我在2.5节里写过的统计min用num - min做偏移。这个处理其实也涵盖了负数输入的情况。另外回填的时候一定别忘了把偏移加回来nums[index] i min。我自己就栽过好几次统计完直接写了nums[index] i结果所有元素都整体偏小了。4.3 库函数与手写排序的取舍LeetCode上不少题目你确实可以直接调用Arrays.sort()但我建议在练习阶段还是尽量手写排序特别是快排和计数排序。原因有两点第一很多题目虽然题目描述不要求手写排序但思路本身和排序无关时调用库函数当然没问题可如果考点就是排序本身你却调了库函数那就没达到练习目标。第二面试手撕代码时很多面试官会直接问“能不能不用库函数实现”与其当场临时回忆不如平时多写两遍。4.4 实战题目速查表为了方便大家刷题时快速定位我把LeetCode上几个常见的和排序强相关的题目类型整理一下题目类型推荐排序思路备注数组中的第K个最大元素快速选择QuickSelect快排partition的变种平均O(n)颜色分类三指针一次遍历荷兰国旗问题类似三向切分对链表进行插入排序插入排序链表版注意链表不能随机访问排序链表归并排序 / 快排链表版要求O(n log n)、O(1)空间多数元素 / 出现次数统计排序后取中间值也可用摩尔投票法最小绝对差排序后相邻比较排序是起点本身不是考点按频率排序字符串/数组计数排序 / 优先队列数据范围有限时计数排序更高效5. 一个综合案例从零实现手写排序工具类讲了这么多原理和技巧我来带大家动手实践一个“综合案例”写一个手写排序工具类支持五种排序算法并且做统一入口。这不光是一个练习也能成为你自己的“算法工具箱”后续刷题时直接复用。我个人的设计思路是这样每个排序方法只接收int[] nums作为参数内部自行处理边界。快排因为需要递归单独再拆一个私有方法。public class SortUtils { // 冒泡排序 public static void bubbleSort(int[] nums) { int n nums.length; for (int i 0; i n - 1; i) { boolean swapped false; for (int j 0; j n - 1 - i; j) { if (nums[j] nums[j 1]) { int tmp nums[j]; nums[j] nums[j 1]; nums[j 1] tmp; swapped true; } } if (!swapped) return; } } // 选择排序 public static void selectionSort(int[] nums) { int n nums.length; for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (nums[j] nums[minIdx]) { minIdx j; } } if (minIdx ! i) { int tmp nums[i]; nums[i] nums[minIdx]; nums[minIdx] tmp; } } } // 插入排序 public static void insertionSort(int[] nums) { int n nums.length; for (int i 1; i n; i) { int cur nums[i]; int j i - 1; while (j 0 nums[j] cur) { nums[j 1] nums[j]; j--; } nums[j 1] cur; } } // 快速排序 public static void quickSort(int[] nums) { quickSort(nums, 0, nums.length - 1); } private static void quickSort(int[] nums, int left, int right) { if (left right) return; // 随机主元降低最坏情况概率 int randIdx left (int) (Math.random() * (right - left 1)); int tmp nums[left]; nums[left] nums[randIdx]; nums[randIdx] tmp; int pivot nums[left]; int i left, j right; while (i j) { while (i j nums[j] pivot) j--; nums[i] nums[j]; while (i j nums[i] pivot) i; nums[j] nums[i]; } nums[i] pivot; quickSort(nums, left, i - 1); quickSort(nums, i 1, right); } // 计数排序 public static void countingSort(int[] nums) { if (nums null || nums.length 1) return; int max nums[0], min nums[0]; for (int num : nums) { max Math.max(max, num); min Math.min(min, num); } int range max - min 1; int[] count new int[range]; for (int num : nums) { count[num - min]; } int index 0; for (int i 0; i range; i) { while (count[i] 0) { nums[index] i min; count[i]--; } } } }写完这个工具类我建议你做的第一件事不是拿去刷题而是自己写一个随机数组生成器生成各种不同规模、不同分布随机、有序、逆序、大量重复的测试数据然后对比每个排序的结果是否正确顺便测一下耗时。这个过程能帮你直观感受到前文讲的复杂度差异数据量5000以内五种排序基本都能秒出结果你感觉不到差别数据量10万冒泡排序会开始变得明显卡顿而快排依然是毫秒级数据量100万插入排序和选择排序已经很难等到结果了快排依然稳定计数排序则要看取值范围。我印象很深的一次测试是生成一个长度为100万、取值范围0到100的数组。计数排序跑完只用了大概几十毫秒而快排大概是一秒多。这个差距不是常数级别的就是算法设计层面的碾压。你可以自己试一试这种体感比看任何复杂度表格都来得深刻。6. 刷题与面试中的实用建议聊得差不多了最后我根据自己的实际经验再整理几条关于排序算法刷题和面试的建议也许能帮你少走点弯路。第一手写代码前先在脑子里过一遍“不变量”。每次写循环之前明确告诉自己这个循环结束后数组一定满足什么条件比如写选择排序的循环时告诉自己“循环进行到i时前i个元素已经是排序好的且不会再被改动”。这个习惯一开始会觉得麻烦但坚持下来代码bug率会大幅降低。第二五种排序里优先级最高的一定是快速排序和计数排序。冒泡、选择、插入这三种你可以三天不看再写一遍大概率还能写出来但快排和计数排序优先理解原理因为它们的变种在LeetCode上真的是高频考点。我认为把快排的partition完全消化比背十个八股题更有价值。第三关于“稳定排序”这个概念如果不理解的建议找一组实际数据手工模拟一遍。这个过程没什么技巧就是拿纸笔画一画。我自己当年就是画了三张纸才彻底弄明白为什么选择排序是不稳定的。第四刷题的时候如果有人跟你讨论“什么排序最好”记住没有万能的答案。快排虽然综合性能强但在数据范围有限时计数排序能把它的复杂度按在地上摩擦插入排序看着慢但在小规模数据上打快排也不是没可能。真正的“最优解”一定是根据场景判断的。第五如果面试中要求手写快排我强烈建议用我在2.4节给的那种“挖坑法”版本配合随机主元。它比我见过的教科书上的经典Hoare版本更不容易写错也更好解释。讲解的时候你可以把“坑”这个概念说出来面试官基本都能听懂也更容易认可你的思路。好了这篇关于排序算法五件套的内容就写到这。这些东西看起来基础但确实是算法学习的“地基”。我始终认为与其追求“我刷了多少题”不如先把这种最底层的东西吃透。排序算法背后涉及的分治、递归、双指针、空间换时间的思想会一路影响你对后面所有算法题的理解。希望这篇文章能帮你把这些思想串起来。