排序算法（上）：冒泡、选择、插入、希尔
排序，是数据结构里最基础也最常考的一块。我个人习惯把排序算法分成两类：一类是简单但慢的，一类是复杂但快的。今天我们先聊前四个——冒泡、简单选择、直接插入、希尔排序。这几个算法，说白了就是帮你把一堆乱序的数据排好。你想想看，数据库里查个成绩、电商里按价格排序，底层都离不开它们。
核心要点：这四种排序的时间复杂度都在 O(n²) 到 O(n log n) 之间。冒泡和选择最慢，插入在数据基本有序时很快，希尔是插入的升级版。
1. 冒泡排序
冒泡排序的思路特别直观：从头到尾，两两比较，把大的往后挪。就像气泡从水底往上冒一样，最大的数会慢慢「浮」到最后面。
我在项目中遇到过一个小问题：数据量只有几百条，用冒泡排序完全够用，但新手容易写错内层循环的边界。嗯，这里要注意——每轮排序后，最后一个元素已经就位，下一轮就不用再比较它了。
void bubble_sort(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; // 没交换说明已经有序
}
}我的小技巧：加一个 swapped 标志位，如果某一轮没有发生交换，说明数组已经有序，直接跳出。这在数据接近有序时能省不少时间。
时间复杂度：最好 O(n)，最坏 O(n²)，平均 O(n²)。空间复杂度 O(1)。稳定排序。
2. 简单选择排序
选择排序的思路更直接：每一轮找到最小的元素，放到最前面。说白了就是「矮子里拔将军」，一轮选一个。
我曾经在嵌入式项目里用过选择排序——因为它的交换次数少，每次只交换一次，对内存写入比较友好。但要注意，它不稳定。举个例子：数组 [5a, 5b, 3]，第一轮会把 3 和 5a 交换，结果 5a 跑到了 5b 后面，顺序就乱了。
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;
}
}
}避坑指南：我曾经在面试题里看到有人把选择排序和冒泡排序搞混。记住：冒泡是相邻比较，选择是选最小值交换。两者虽然都是 O(n²)，但选择排序的交换次数少得多。
时间复杂度：最好、最坏、平均都是 O(n²)。空间复杂度 O(1)。不稳定排序。
3. 直接插入排序
插入排序的思路，就像你打扑克牌时整理手牌——每次摸一张新牌，插入到已经排好序的牌堆里。我个人觉得这是最符合人类直觉的排序方法。
为什么说它好用？因为当数据基本有序时，插入排序的效率极高，接近 O(n)。我在处理日志时间戳排序时经常用它——日志本身按时间生成，偶尔有几条乱序，插入排序几下就搞定了。
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)，最坏 O(n²)，平均 O(n²)。空间复杂度 O(1)。稳定排序。
4. 希尔排序
希尔排序是插入排序的升级版。它先把数组分成若干子序列，对每个子序列做插入排序，然后逐步缩小间隔，直到间隔为 1 时做一次完整的插入排序。
你想想看，插入排序在数据基本有序时很快，但完全乱序时很慢。希尔排序的思路就是：先让数据「大致有序」，再精细调整。我当年学这个算法时觉得它很巧妙——用大间隔跳跃式移动，减少了很多不必要的比较。
void shell_sort(int arr[], int n) {
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;
}
}
}我的经验：希尔排序的时间复杂度跟间隔序列有关。上面代码用的是最简单的 gap = n/2 递减，时间复杂度大约 O(n²)。如果使用 Hibbard 序列（1, 3, 7, 15...），可以降到 O(n^(3/2))。实际项目中我一般用 gap = gap*3 + 1 这个序列，效果不错。
时间复杂度：取决于间隔序列，一般 O(n^(1.3)) 到 O(n²)。空间复杂度 O(1)。不稳定排序。
知识体系总览
下面这张图帮你理清这四种排序的关系和特点：
总结一下
这四种排序，冒泡和选择是最基础的，面试时经常被问到。插入排序在实际开发中很实用，尤其是数据量不大且接近有序时。希尔排序则是一个很好的过渡——它让你看到，通过改变策略，O(n²) 的算法也能提速。
我个人建议你把这四个算法的代码亲手敲一遍，然后跑几个测试用例看看效果。代码写多了，感觉自然就来了。
一句话记住：冒泡相邻比，选择挑最小，插入像打牌，希尔分组插。
公众号:蓝海资料掘金营，微信deep3321