排序算法（一）：冒泡排序、选择排序、插入排序、希尔排序
排序，是数据结构与算法里最基础、也最常考的内容。说实话，我工作十几年了，面试新人时还是喜欢从排序聊起。为什么？因为排序算法能看出一个人的基本功——对循环的理解、对复杂度的敏感、对代码细节的把控。
这一章我们聊四个经典排序：冒泡、选择、插入、希尔。它们都属于比较排序，时间复杂度从 O(n²) 到 O(n log n) 不等。我会结合自己的踩坑经历，把每个算法的核心逻辑、代码实现、以及实际应用场景讲清楚。
本章核心知识点
- 冒泡排序：相邻元素两两比较，大的往后冒
- 选择排序：每次选最小的，放到已排序末尾
- 插入排序：像打扑克牌一样，把新牌插入到合适位置
- 希尔排序：插入排序的升级版，先分组再排序
1. 冒泡排序
冒泡排序的思路很简单：从头到尾，两两比较相邻元素，如果前一个比后一个大，就交换。这样一轮下来，最大的元素就「冒」到了最后。重复这个过程，直到所有元素有序。
我记得刚学编程时，老师用一杯水里的气泡来比喻——大的气泡先浮上去。嗯，这个比喻挺形象的。
// 冒泡排序 - 标准实现
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 每轮比较次数递减
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}优化小技巧
如果某一轮没有发生任何交换，说明数组已经有序了。可以加一个标志位提前退出。我在项目中处理接近有序的数据时，这个优化能省不少时间。
// 冒泡排序 - 优化版（带提前退出）
void bubble_sort_optimized(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (!swapped) break; // 没有交换，提前结束
}
}时间复杂度：最好 O(n)，最坏 O(n²)，平均 O(n²)。
空间复杂度：O(1)，原地排序。
稳定性：稳定。相等的元素不会交换位置。
2. 选择排序
选择排序的思路更直接：每一轮找到未排序部分的最小元素，把它放到已排序部分的末尾。说白了，就是「矮子里拔将军」，每次挑一个最小的放前面。
我曾经在一个嵌入式项目里用过选择排序——数据量很小（不到100个），而且对稳定性没要求。选择排序的交换次数少，在某些场景下反而比冒泡快。
// 选择排序
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 temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
}注意：选择排序是不稳定的
举个例子：数组 [5a, 5b, 3]，第一轮会把 3 和 5a 交换，结果变成 [3, 5b, 5a]。两个 5 的相对顺序变了。如果你需要稳定排序，别用选择排序。
时间复杂度：最好 O(n²)，最坏 O(n²)，平均 O(n²)。
空间复杂度：O(1)。
稳定性：不稳定。
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)
- 数据量小（<50）时，比很多 O(n log n) 算法都快
- 稳定排序，适合对稳定性有要求的场景
时间复杂度：最好 O(n)，最坏 O(n²)，平均 O(n²)。
空间复杂度：O(1)。
稳定性：稳定。
4. 希尔排序
希尔排序是插入排序的改进版。它解决了插入排序的一个痛点：每次只能移动一个位置。如果最小的元素在最后面，插入排序要移动 n-1 次才能把它放到最前面。
希尔排序的做法是：先分组，对每组进行插入排序。然后缩小分组间隔，再排序。直到间隔为 1，就是一次完整的插入排序。
我记得第一次看希尔排序时，觉得这思路挺巧的——先让数组「基本有序」，最后再用插入排序收尾。这样既利用了插入排序在基本有序时的高效，又避免了大量移动。
// 希尔排序
void shell_sort(int arr[], int n) {
// 初始间隔为 n/2，每次减半
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个分组进行插入排序
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}关于间隔序列
上面用的是最简单的间隔序列（每次除以2）。实际工程中，有更好的选择，比如 Hibbard 序列（1, 3, 7, 15...）或 Sedgewick 序列。不同的间隔序列会影响时间复杂度。我一般用 n/2 递减，简单够用。
时间复杂度：取决于间隔序列。最坏 O(n²)，平均约 O(n log n) ~ O(n^1.3)。
空间复杂度：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 log n) | O(n²) | O(n^1.3) | O(1) | 不稳定 | 中等数据量 |
避坑指南：我曾经犯过的错
我曾经在嵌入式设备上处理传感器数据排序，数据量大概 200 个左右。一开始用了冒泡排序，结果发现每次排序要跑好几毫秒，设备响应变慢。后来换成希尔排序，时间降到了不到 1 毫秒。所以啊，别小看排序算法的选择，在资源受限的环境里，这点差距可能就是能不能用的区别。
好了，这四种排序就聊到这里。它们虽然简单，但理解透了，后面学快速排序、归并排序时就会轻松很多。记住：没有最好的排序，只有最合适的排序。根据数据量、有序程度、稳定性要求来选，才是工程师该有的思路。