排序算法这五件套,说穿了就是算法面试的“基本功试金石”。不管你是刚刷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 很小(比如 K=1 或 K=2)时,这个做法比整体排序还快。
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[j+1],结果当前元素的值就被丢掉了。
第二,内层循环从 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]这样的数组,你如果直接开max+1长度的数组会有大量空间浪费。用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版本更不容易写错,也更好解释。讲解的时候,你可以把“坑”这个概念说出来,面试官基本都能听懂,也更容易认可你的思路。
好了,这篇关于排序算法五件套的内容就写到这。这些东西看起来基础,但确实是算法学习的“地基”。我始终认为,与其追求“我刷了多少题”,不如先把这种最底层的东西吃透。排序算法背后涉及的分治、递归、双指针、空间换时间的思想,会一路影响你对后面所有算法题的理解。希望这篇文章能帮你把这些思想串起来。