排序算法（一）：冒泡排序、选择排序、插入排序、希尔排序
排序，是数据结构里最基础、也最常考的内容。我个人习惯把排序算法分成两类：一类是简单直观的，适合入门；另一类是高效但稍复杂的，适合实战。今天我们先聊第一类——冒泡、选择、插入和希尔排序。
你想想看，这些算法虽然在实际工程中很少直接使用（因为 O(n²) 的复杂度在大数据量下扛不住），但它们的思路是后续高级排序的基石。我当年刚学的时候，就是靠手写这四种排序，才真正理解了“循环嵌套”和“交换”这两个核心概念。
核心要点：这四种排序都属于“比较排序”，即通过比较元素大小来决定顺序。它们的区别在于“如何比较”和“如何移动”。
1. 冒泡排序：最直观的“交换”
冒泡排序的思路很简单：从头到尾，两两比较相邻元素，如果顺序不对就交换。每一趟下来，最大的元素就像气泡一样“浮”到末尾。
我记得第一次写冒泡时，总搞不清内层循环的边界。后来我总结了一个口诀：外层控制趟数，内层控制比较范围。
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) { // 趟数：n-1趟
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;
}
}
}
}小优化：如果某一趟没有发生任何交换，说明数组已经有序，可以提前结束。加一个 flag 变量即可。我在项目中处理接近有序的数据时，这个优化能省不少时间。
2. 选择排序：每趟选一个“最值”
选择排序的思路更直接：每一趟从待排序区间中选出最小的元素，放到已排序区间的末尾。说白了，就是“矮子里拔将军”，一趟选一个。
它和冒泡的区别在于：冒泡是“边比边换”，选择是“先比后换”。所以选择排序的交换次数更少，但比较次数一样多。
void selection_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i; // 假设当前是最小值
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j; // 记录真正的最小值位置
}
}
if (min_idx != i) { // 交换
int tmp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = tmp;
}
}
}注意：选择排序是不稳定的。举个例子：数组 [5a, 5b, 3]，第一趟会把 3 和 5a 交换，结果变成 [3, 5b, 5a]，两个 5 的相对顺序变了。如果你需要稳定排序，别用选择。
3. 插入排序：像整理扑克牌
插入排序的思路，你玩过扑克牌就懂了。每次摸一张新牌，把它插入到手中已排好序的牌里合适的位置。
具体做法：把数组分成“已排序”和“未排序”两部分。每次从“未排序”中取第一个元素，在“已排序”中从后往前找，找到合适位置插入。
void insertion_sort(int arr[], int n) {
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; // 插入到正确位置
}
}插入排序有一个很实用的特性：当数据基本有序时，它的效率接近 O(n)。我曾经在项目中处理日志时间戳排序，数据本身已经按时间大致排好了，用插入排序比用快排还快——因为快排的递归开销太大了。
实战建议：插入排序是“自适应”的，数据越有序，它越快。如果你的数据量不大（比如几百个），或者数据接近有序，插入排序是很好的选择。
4. 希尔排序：插入排序的“升级版”
希尔排序是插入排序的改进版。它解决了插入排序的一个痛点：每次只能移动一个位置。如果最小的元素在末尾，插入排序要移动 n-1 次才能把它放到最前面。
希尔排序的做法是：先分组，组内用插入排序。然后逐步缩小分组，最后整个数组基本有序时，再做一次完整的插入排序。
void shell_sort(int arr[], int n) {
// 增量序列：n/2, n/4, ..., 1
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个分组进行插入排序
for (int i = gap; i < n; i++) {
int key = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > key) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = key;
}
}
}你看，代码和插入排序很像，区别就在于比较和移动的步长变成了 gap，而不是 1。
关于增量序列：我上面用的是最简单的 n/2 递减，实际还有更优的序列（比如 Hibbard 序列、Sedgewick 序列）。不过对于教学来说，n/2 递减已经足够展示希尔排序的核心思想了。
5. 四种排序的对比总结
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | 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^1.3) ~ O(n²) | O(n log n) | O(n²) | O(1) | 不稳定 |
避坑指南：我曾经在面试中遇到过一道题——要求用 O(1) 额外空间对链表排序。我当时第一反应是快排，但快排需要递归栈空间。后来我用了插入排序，因为链表插入不需要移动元素，只需要改指针，空间复杂度完美满足 O(1)。所以，别小看这些“简单”的排序，它们在某些场景下反而是最优解。
6. 我的学习建议
如果你刚开始学排序，我建议你按这个顺序来：
- 先手写冒泡和选择——理解“比较”和“交换”的基本操作。
- 再写插入排序——理解“局部有序”和“插入”的思想。
- 最后攻克希尔排序——理解“分组”和“逐步精细”的策略。
每写一个算法，都自己画一遍执行过程。比如数组 [5, 3, 8, 6, 2]，手动模拟每一趟的变化。这个过程很枯燥，但效果极好。我当年就是这么过来的，画了不下 50 张草稿纸。
嗯，四种排序讲完了。它们虽然简单，但每个都有自己独特的应用场景。记住：没有最好的排序，只有最合适的排序。