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

实现思路

1. 分组策略：设定初始间隔 gap，通常取数组长度的三分之一左右。
2. 预排序：按照 gap 的距离进行插入排序。例如 gap=3，则索引 0, 3, 6... 为一组，1, 4, 7... 为一组，分别排序。
3. 缩小间隔：每轮排序后，gap 值减小，直到 gap 变为 1。
4. 最终排序：当 gap=1 时，相当于对整个数组进行一次标准的插入排序，此时由于数组已基本有序，效率极高。

关于 gap 的取值，经验表明使用 gap = gap / 3 + 1 的递减方式效果较好，既能保证快速收敛，又能确保最后一次 gap 恰好为 1。

代码实现

// 希尔排序
void ShellSort(int* a, int n) {
    int gap = n;
    while (gap > 1) {
        // 动态调整 gap，确保最后一步 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;
        }
    }
}

在这个实现中，内层逻辑与插入排序几乎一致，唯一的区别是将步长 1 换成了当前的 gap 值。这种设计既复用了插入排序的逻辑，又通过间隔跳跃提升了整体性能。

总结

插入排序适合小规模或基本有序的数据，代码简单且稳定。而希尔排序通过引入间隔机制优化了插入排序的性能，是处理中等规模数据时的优选方案。理解这两种算法的核心差异，有助于在实际开发中根据数据特征做出更合理的排序选择。