C 语言排序算法详解：插入排序与希尔排序

希尔排序

算法思想

希尔排序（Shell Sort）本质上是插入排序的一种改进版本。它通过引入一个间隔参数 gap，将数组分成若干个子序列进行预排序。随着 gap 逐渐减小，子序列越来越长，数组整体也越来越接近有序状态。最后一次 gap 为 1 时，执行标准的插入排序，此时由于数组已基本有序，效率会大幅提升。

实现思路

1. 分组策略

不再逐个元素比较，而是每隔 gap 个元素分为一组。例如 gap=3 时，索引 0, 3, 6... 为一组，1, 4, 7... 为一组，每组内部独立进行插入排序。

2. 预排序与最终排序

• 预排序：使用较大的 gap 进行多轮分组排序，使大跨度元素快速移动到相对正确的位置。
• 最终排序：当 gap 缩小至 1 时，相当于对整个数组进行一次插入排序。由于之前的预排序已经让数据'局部有序'，这一步的移动次数会显著减少。

3. Gap 的取值

gap 的选取直接影响性能。常见的经验公式是 gap = gap / 3 + 1。这种取法能保证 gap 在递减过程中始终大于 1，且最后一次循环恰好为 1，从而自然衔接标准插入排序。

代码实现

// 希尔排序
void ShellSort(int* a, int n) {
    int gap = n;
    while (gap > 1) {
        gap = gap / 3 + 1;
        for (int i = 0; i < n - gap; i++) {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0) {
                if (tmp < a[end]) {
                    a[end + gap] = a[end];
                    end -= gap;
                } else {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}

在这个实现中，外层循环控制 gap 的变化，内层循环则复用插入排序的逻辑，只是将步长从 1 替换为了当前的 gap 值。这种结构既保证了代码的简洁性，又实现了算法的优化效果。

总结

插入排序适合小规模或部分有序的数据，时间复杂度为 O(n²)。而希尔排序通过分组预排序，有效减少了数据移动的次数，平均时间复杂度优于普通插入排序。理解这两种算法的演变关系，有助于掌握更复杂排序算法的设计思路。