元数据卡
| 属性 | 值 |
|---|---|
| 难度 | 基础 |
| 前置 | 数组、循环、递归 |
| 关键词 | 冒泡排序 · 选择排序 · 插入排序 · 稳定性 · O(n^2) |
| 预计阅读 | 15 分钟 |
你的进度
你面前有一堆杂乱无章的物品（一个整型数组），你想让它们从小到大排好。最简单的办法？"把最小的挑出来放前面"——选择排序。"相邻对比，大的往后浮"——冒泡排序。"像理扑克牌一样逐张插入"——插入排序。三种方法都很直观，但代价都是 O(n^2)。数据量少时够用，大数据面前你则需要更聪明的策略——那是下一站的内容。
你的任务
读完这一页，你应当能：徒手写出三种排序的 Java 实现；说出谁交换最少、谁最稳定、谁对几乎有序的数据最快；理解稳定性为什么重要。目标很直接，动手吧。
冒泡排序：像气泡从水底往上浮
核心直觉：相邻元素两两比较，大的往右浮。 每轮结束，当前范围内最大的元素被浮到最右边。
以一 [5, 3, 8, 1] 为例：
[5, 3, 8, 1] 比较 5 和 3 → 交换
[3, 5, 8, 1] 比较 5 和 8 → 不动
[3, 5, 8, 1] 比较 8 和 1 → 交换
[3, 5, 1, 8] ← 第一轮结束，8 已就位Java 实现
public class BubbleSort {
// 运行: javac BubbleSort.java && java BubbleSort
// 输出: [1, 2, 4, 5, 8]
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
swapped = true;
}
}
if (!swapped) break; // 没有交换 → 已有序
}
}
public static void main(String[] args) {
int[] data = {5, 1, 4, 2, 8};
bubbleSort(data);
System.out.println(java.util.Arrays.toString(data));
}
}这里的 swapped 标志是优化点：如果一轮遍历没有发生交换，数组已经有序，可以提前终止。最好情况降到 O(n)。
复杂度
| 场景 | 时间 | 空间 | 稳定 |
|---|---|---|---|
| 最好（已有序） | O(n) | O(1) | 稳定 |
| 平均 / 最坏 | O(n^2) | O(1) | 稳定 |
冒泡的交换次数是三种 O(n^2) 排序里最多的，常数也最大。它的教学价值在于：交换是排序最朴素的原子操作，所有更快的算法都在思考"能不能少交换几次"。
选择排序：每轮选最小的
核心直觉：每轮找出剩余部分的最小值，放到当前位置。 像在一堆杂物里反复挑最轻的。
初始: [29, 10, 14, 37, 13]
第1轮: 找最小值 10，交换到位置 0 → [10, 29, 14, 37, 13]
第2轮: 找最小值 13，交换到位置 1 → [10, 13, 14, 37, 29]
第3轮: 在 [14, 37, 29] 中 14 已在位 → 不动
第4轮: 找最小值 29，交换到位置 3 → [10, 13, 14, 29, 37]每轮只做一次交换，所以交换次数最少——这是选择排序唯一的亮点。
Java 实现
public class SelectionSort {
// 运行: javac SelectionSort.java && java SelectionSort
// 输出: [11, 12, 22, 25, 64]
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
int tmp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = tmp;
}
}
public static void main(String[] args) {
int[] data = {64, 25, 12, 22, 11};
selectionSort(data);
System.out.println(java.util.Arrays.toString(data));
}
}复杂度
| 场景 | 时间 | 空间 | 稳定 |
|---|---|---|---|
| 全部 | O(n^2) | O(1) | 不稳定 |
关键缺陷：即使输入有序也要跑完两层循环；跨越位置的 swap 会打乱相等元素顺序——所以不稳定。
插入排序：打牌理牌法
核心直觉：把当前牌插入到已排序牌堆的正确位置。 摸一张新牌，从右到左看，找到合适的位置插进去。
初始: [12, 11, 13, 5, 6]
第1轮(key=11): [11, 12, 13, 5, 6] ← 11 插到 12 前面
第2轮(key=13): [11, 12, 13, 5, 6] ← 13 已在位
第3轮(key=5): [5, 11, 12, 13, 6] ← 5 一路左移
第4轮(key=6): [5, 6, 11, 12, 13] ← 完成关键操作是后移腾位：找到插入位置后，把该位置及之后元素右移一位，再放 key。
Java 实现
public class InsertionSort {
// 运行: javac InsertionSort.java && java InsertionSort
// 输出: [5, 6, 11, 12, 13]
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 后移腾位
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] data = {12, 11, 13, 5, 6};
insertionSort(data);
System.out.println(java.util.Arrays.toString(data));
}
}为什么重要？ 两个好性质：1) 对几乎有序的数据 O(n) —— 内层 while 几乎不执行；2) 稳定 —— 相等时不交换。这让它成为 TimSort 的基石。
复杂度
| 场景 | 时间 | 空间 | 稳定 |
|---|---|---|---|
| 最好（已有序） | O(n) | O(1) | 稳定 |
| 平均 / 最坏 | O(n^2) | O(1) | 稳定 |
稳定性：为什么在乎？
如果两个相等元素排序后相对位置不变，算法就是稳定的。比如学生名单已按学号排好，你再按分数排序——稳定排序保证同分者仍按学号顺序。
| 算法 | 稳定？ | 原因 |
|---|---|---|
| 冒泡排序 | 稳定 | 相邻比较，> 才交换，相等不动 |
| 选择排序 | 不稳定 | 跨越 swap 打乱相等元素顺序 |
| 插入排序 | 稳定 | > 才后移，相等不动 |
旅人笔记
三种 O(n^2) 排序各有定位：选择排序交换最少但不稳定，冒泡排序稳定但最慢，插入排序在几乎有序时 O(n) 且稳定——后者是它成为高级排序基石的原因。