排序算法入门（一）：三种 O(n²) 排序 —— 冒泡、选择、插入
为什么慢排序还值得写
线上导出那次事故很典型：有人在一个循环里套了一层循环找每个分组的最小时间戳，接口从 80 毫秒变成 40 秒。问题不在于他"没听过快排"，而在于没意识到自己写的就是选择排序——这个规模下 O(n²) 意味着百亿次比较。
这三种算法真正的价值是三个判断标准：数据小到什么程度时"慢算法反而更快"、"近乎有序"为什么值钱、稳定性在业务里怎么生效。
我第一次写冒泡时把内层边界写成 i < a.length - 1，外层又拿 i 当轮次，结果最后一个元素永远沉不到末尾。测试还是绿的，因为用例恰好是逆序数据。
冒泡排序
核心思想
相邻两个元素比较，大的往后换。每轮走完，未排序区间的最大值一定被推到最右端，右边界随之收窄。加上"本轮无交换就提前结束"，已经有序的输入只需扫一轮。
以 {5, 1, 4, 2, 8} 为例（加粗表示本轮结束后确定归位的部分）：
| 轮次 | 比较区间 | 本轮交换 | 结束后 |
|---|---|---|---|
| 第 1 轮 | 下标 0..4 | 5 依次与 1、4、2 交换 | 1 4 2 5 8 |
| 第 2 轮 | 下标 0..3 | 4 与 2 交换 | 1 2 4 5 8 |
| 第 3 轮 | 下标 0..2 | 一次交换都没有 | 判定有序，直接结束 |
第三轮就是提前退出的那一步，省下的是整轮扫描而非某次比较。
代码
java
import java.util.Arrays;
public class BubbleSort {
public static void sort(int[] a) {
if (a == null || a.length < 2) {
return;
}
// end 是未排序区间的右边界：每轮跑完，a[end] 一定是这个区间里的最大值
for (int end = a.length - 1; end > 0; end--) {
boolean swapped = false; // 记录本轮是否真的换过，用于提前退出
for (int i = 0; i < end; i++) {
if (a[i] > a[i + 1]) { // 写成 >= 会破坏稳定性，相等时不换
int t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
swapped = true;
}
}
// 一轮下来没有任何交换，说明区间已经有序，再跑都是白费
if (!swapped) {
break;
}
}
}
public static void main(String[] args) {
int[] a = {5, 1, 4, 2, 8};
sort(a);
System.out.println(Arrays.toString(a)); // [1, 2, 4, 5, 8]
int[] alreadySorted = {1, 2, 3, 4, 5};
sort(alreadySorted); // 只扫一轮就退出，比较次数是 n-1
System.out.println(Arrays.toString(alreadySorted));
}
}复杂度分析
最好 O(n)：输入已经有序，优化后的版本只做一轮 n-1 次比较就退出。平均和最坏都是 O(n²)，完全逆序时比较与交换都达到 n(n-1)/2 次。空间 O(1)，原地排序，稳定：只有 a[i] > a[i+1] 才交换，相等元素不会跨越彼此。
选择排序
核心思想
每一轮在未排序区间里找出最小值，和区间首位交换。比较次数固定，但交换次数是所有常见排序里最少的。
| 轮次 | 未排序区间 | 本轮最小值 | 交换后 |
|---|---|---|---|
| 第 1 轮 | 5 1 4 2 8 | 1（下标 1） | 1 5 4 2 8 |
| 第 2 轮 | 5 4 2 8 | 2（下标 3） | 1 2 4 5 8 |
| 第 3 轮 | 4 5 8 | 4（本来就在首位） | 1 2 4 5 8 |
代码
java
import java.util.Arrays;
public class SelectionSort {
public static void sort(int[] a) {
if (a == null || a.length < 2) {
return;
}
for (int i = 0; i < a.length - 1; i++) {
int minIndex = i; // 先假设未排序区间的首位就是最小值
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[minIndex]) { // 严格小于：保留最靠前的那个最小值
minIndex = j;
}
}
// 内层只记录下标，交换发生在外层，总交换次数因此不超过 n-1
if (minIndex != i) {
int t = a[i];
a[i] = a[minIndex];
a[minIndex] = t;
}
}
}
public static void main(String[] args) {
int[] a = {5, 1, 4, 2, 8};
sort(a);
System.out.println(Arrays.toString(a)); // [1, 2, 4, 5, 8]
}
}复杂度分析
最好、平均、最坏全是 O(n²)，这点最容易答错：内层必须扫完整个未排序区间才知道最小值是谁，没有提前退出的机会，输入有序也救不了它。空间 O(1)，原地排序，交换次数 O(n) —— 元素很大或者写操作昂贵时这是真实优势。
它不稳定。{(5,A), (5,B), 1} 第一轮把下标 0 的 5 与下标 2 的 1 交换，变成 1, (5,B), (5,A)，两个 5 的次序被反转。
插入排序
核心思想
把数组想成左手已经理好的牌和右手还没摸的牌。每次取右手第一张，在左手从右往左找位置插进去，比它大的牌整体右挪一格。前缀始终有序，但元素不一定在最终位置上，这点和选择排序相反。
| 轮次 | 已排序前缀 | 当前元素 | 前缀变化 |
|---|---|---|---|
| 初始 | 5 | — | 5 1 4 2 8 |
| 第 1 轮 | 5 | 1 | 1 5 4 2 8 |
| 第 2 轮 | 1 5 | 4 | 1 4 5 2 8 |
| 第 3 轮 | 1 4 5 | 2 | 1 2 4 5 8 |
| 第 4 轮 | 1 2 4 5 | 8 | 一次比较就结束：比前缀最大值还大 |
最后一行是它和另外两种排序的关键差别：新元素比前缀最大值还大时，只有一次比较、零次挪动。
代码
java
import java.util.Arrays;
public class InsertionSort {
public static void sort(int[] a) {
if (a == null || a.length < 2) {
return;
}
for (int i = 1; i < a.length; i++) {
int cur = a[i]; // 先把待插入元素取出来，后面整体后移会覆盖 a[i]
int j = i - 1;
// 从右往左找位置：比 cur 大的都右挪一格，直到遇到不大于 cur 的
while (j >= 0 && a[j] > cur) { // 写成 >= 会把相等元素挪到后面，破坏稳定性
a[j + 1] = a[j];
j--;
}
a[j + 1] = cur; // 循环退出时 j 指向不大于 cur 的元素，空位就是 j+1
}
}
public static void main(String[] args) {
int[] a = {5, 1, 4, 2, 8};
sort(a);
System.out.println(Arrays.toString(a)); // [1, 2, 4, 5, 8]
// 近乎有序的输入：只有 8 和 5 逆序，挪动次数极少
int[] nearlySorted = {1, 2, 3, 4, 5, 6, 7, 9, 8, 10};
sort(nearlySorted);
System.out.println(Arrays.toString(nearlySorted));
}
}复杂度分析
最好 O(n)：输入有序时每个元素只和自己的前驱比较一次，不进入移位循环。平均和最坏是 O(n²)，完全逆序时第 i 个元素要挪 i 次，合计 n(n-1)/2 次移动。空间 O(1)，原地排序，稳定。常数因子很小：内层就是一次比较加一次数组写入，没有函数调用，小规模下跑赢快排很常见。
复杂度与稳定性对照
| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定性 | 是否原地 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 是 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 是 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 是 |
冒泡和插入的 O(n) 都依赖提前结束这个前提：冒泡固定跑满 n-1 轮、插入写成两两交换，最好情况都会退化成 O(n²)。
工程里它们真的还在用
JDK 自己就在用插入排序。Arrays.sort(Object[]) 走 TimSort：先把输入切成若干自然有序的 run，长度不足 minRunLength（32 到 64）时用二分插入排序补齐——二分定位插入点把比较次数压到 O(log k)，再用 System.arraycopy 整段挪内存，短区间上比启动快排框架便宜。Arrays.sort(int[]) 对基本类型走双轴快排，长度不到几十个元素时同样切回插入排序，因为递归分治比元素本身还贵。
近乎有序的场景更能说明问题。维护一份按时间排好的日志、每小时补几条迟到记录时，插入排序的代价是 O(n + k)，k 是逆序对的数量，迟到记录不多时几乎是线性的；快排面对同样的输入仍要做完整分区，n log n 一分不少，没做随机化选主元的实现还会因为有序输入退化成 O(n²)。所以"数据基本有序"直接决定该选谁。
稳定性也有具体后果：要"按金额排序、金额相同的保持原下单顺序"，就先按时间排，再用稳定排序按金额排一次；这一步若用了选择排序或者快排，相同金额的记录顺序会随机变化，前端列表每次刷新都在跳。
小结
三种算法可以按"怎么看待未排序区间"来记：冒泡靠相邻交换把最大值推出去，选择靠扫描挑最小值换进来，插入靠把新元素挪进已有的有序前缀。选择排序无论输入如何都是 O(n²)，换来的是最少的数据写入。
下一篇沿复杂度台阶往上走，写归并和快速排序，重点放在分治的边界处理、主元选择对最坏情况的影响，以及小数组处切回插入排序的工程取舍。
评论