排序之插入与希尔：直接插入排序、折半插入排序、希尔排序
排序算法，是数据结构里的基本功。我个人觉得，插入排序这一族算法，特别能体现「从简单到优化」的思维过程。今天咱们就聊聊直接插入排序、折半插入排序，还有那个让人又爱又恨的希尔排序。
一、直接插入排序——最朴素的思路
直接插入排序，说白了就是打扑克牌时理牌的手法。你摸到一张新牌，从右往左看，找到合适的位置插进去。这个过程，就是直接插入排序的核心。
它的工作原理是这样的：把待排序的数组分成两个区域——已排序区和未排序区。每次从未排序区取出第一个元素，在已排序区从右向左扫描，找到合适的位置插入。
核心要点：直接插入排序在基本有序的序列上表现极好，时间复杂度可接近 O(n)。但在完全逆序时，会退化到 O(n²)。
// 直接插入排序——C语言实现
void insertSort(int arr[], int n) {
int i, j, key;
for (i = 1; i < n; i++) {
key = arr[i]; // 摸到的新牌
j = i - 1;
// 从右向左找插入位置
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // 插入
}
}这段代码我写过无数遍。嗯，这里要注意：内层循环的条件是 arr[j] > key，这意味着相等的元素不会交换位置。所以直接插入排序是稳定的排序算法。
我的经验：我在项目中遇到过需要排序的数据量很小（比如几十个元素），而且数据本身已经接近有序的场景。直接插入排序跑起来，比快排还快。因为快排的递归开销在这种场景下反而成了负担。
二、折半插入排序——减少比较次数
直接插入排序有个明显的缺点：每次都要从右向左逐个比较。如果已排序区很大，比较次数就很多。那能不能用二分查找来加速呢？当然可以。这就是折半插入排序。
折半插入排序的思路是：在已排序区用二分查找找到插入位置，然后统一移动元素。比较次数从 O(n) 降到了 O(log n)，但移动次数仍然是 O(n)。
// 折半插入排序——C语言实现
void binaryInsertSort(int arr[], int n) {
int i, j, key, left, right, mid;
for (i = 1; i < n; i++) {
key = arr[i];
left = 0;
right = i - 1;
// 二分查找插入位置
while (left <= right) {
mid = (left + right) / 2;
if (arr[mid] > key)
right = mid - 1;
else
left = mid + 1;
}
// 移动元素
for (j = i - 1; j >= left; j--)
arr[j + 1] = arr[j];
arr[left] = key;
}
}为什么二分查找的条件是 arr[mid] > key 时往左走，否则往右走？因为我们要保证稳定性。当 arr[mid] == key 时，我们把新元素插到右边，这样相等元素的相对顺序就不会改变。
避坑指南：我曾经在实现折半插入排序时，把二分查找的边界条件写错了。left 和 right 的更新逻辑搞反了，结果排序结果完全不对。后来我养成了一个习惯：每次写完二分查找，先用小数据手动跑一遍边界情况。
折半插入排序的时间复杂度仍然是 O(n²)，因为移动元素的开销没变。它只是减少了比较次数，对于比较操作代价高昂的场景（比如字符串排序）很有价值。
三、希尔排序——跨越式的改进
希尔排序，是插入排序的「升级版」。它的核心思想是：先让序列「基本有序」，然后再用插入排序收尾。怎么做到基本有序？通过增量分组。
希尔排序的工作原理：选择一个增量序列，比如 {5, 3, 1}。先按增量 5 分组，对每组进行插入排序；然后按增量 3 分组，再排序；最后按增量 1（就是普通的插入排序）收尾。
// 希尔排序——C语言实现
void shellSort(int arr[], int n) {
int gap, i, j, key;
// 增量序列：n/2, n/4, ..., 1
for (gap = n / 2; gap > 0; gap /= 2) {
for (i = gap; i < n; i++) {
key = arr[i];
j = i - gap;
while (j >= 0 && arr[j] > key) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = key;
}
}
}你想想看，为什么希尔排序比直接插入排序快？因为经过前面几轮「粗调」，序列已经基本有序了。最后一轮插入排序时，元素移动的距离大大缩短。
增量序列的选择
增量序列的选择，直接决定了希尔排序的性能。我整理了几种常见的增量序列：
| 增量序列 | 递推公式 | 时间复杂度 | 特点 |
|---|---|---|---|
| Shell 原始序列 | gap = n/2, n/4, ..., 1 | O(n²) | 简单，但最坏情况差 |
| Hibbard 序列 | 2^k - 1 | O(n^(3/2)) | 相邻增量互质，性能好 |
| Sedgewick 序列 | 9*4^k - 9*2^k + 1 或 4^k - 3*2^k + 1 | O(n^(4/3)) | 实际表现优秀 |
| Knuth 序列 | (3^k - 1) / 2 | O(n^(3/2)) | 工程中常用 |
重要提醒：希尔排序是不稳定的排序算法。为什么？因为分组排序时，相等的元素可能被分到不同的组，它们的相对顺序就无法保证了。我在项目中用过希尔排序，但前提是我不关心稳定性。
四、排序的稳定性分析
稳定性，说白了就是：两个相等的元素，排序后谁在前谁在后？如果原来的相对顺序保持不变，就是稳定的；否则就是不稳定的。
咱们来总结一下今天讲的三种排序的稳定性：
- 直接插入排序：稳定。因为遇到相等元素时，我们把它插到右边，不改变相对顺序。
- 折半插入排序：稳定。二分查找时，相等时往右找，保证了稳定性。
- 希尔排序：不稳定。分组排序时，相等的元素可能被分到不同组，顺序就乱了。
我的建议：如果你需要稳定的排序，优先考虑归并排序或插入排序。希尔排序虽然快，但不稳定。我曾经在一个数据库项目中，因为用了不稳定的排序导致数据对不上，排查了半天才发现是稳定性问题。
五、知识体系总览
下面这张图，把今天讲的内容串起来了。你可以看到三种排序之间的关系，以及增量序列的选择路径。
从这张图可以看得很清楚：直接插入排序是基础，折半插入排序在比较次数上做了优化，而希尔排序则在移动次数上做了跨越式的改进。三种排序各有适用场景，没有银弹。
总结一下：
- 数据量小且基本有序 → 直接插入排序
- 比较操作代价高 → 折半插入排序
- 数据量大且不要求稳定 → 希尔排序
- 需要稳定排序 → 别用希尔，用直接插入或归并
好了，今天的内容就到这里。排序算法是基本功，多写几遍代码，多跑几个测试用例，自然就熟了。