数据结构入门：插入排序详解（直接插入与希尔排序）

怎么分组呢？不是挨着分，而是跳跃式分组。比如间隔为 2，把距离为 2 的元素看作一组分别排序。这样局部有序的同时，也能让全局数据分布更均匀。如果只按相邻分组，排序后可能只是局部有序，整体依然杂乱。

分组间隔用 gap 表示。初始 gap 设为数组长度，之后每次缩小，通常采用 gap = gap / 3 + 1 的策略。随着 gap 减小，分组变密，直到 gap = 1 时进行最后一次直接插入排序。此时数组已经接近有序，插入操作会非常快。

注意循环条件，当 gap == 1 时仍需执行一次排序，但为了避免死循环，外层 while 判断条件为 gap > 1。

// 希尔排序
void ShellSort(int* arr, 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 = arr[end + gap];
            while (end >= 0) {
                if (arr[end] > tmp) {
                    arr[end + gap] = arr[end];
                    end -= gap;
                } else {
                    break;
                }
            }
            arr[end + gap] = tmp;
        }
    }
}

希尔排序的时间复杂度分析比较复杂，取决于 gap 序列的选择。严蔚敏《数据结构》中给出的估算约为 O(N^1.3)，远优于直接插入排序的 O(N^2)。

三、性能对比

理论上看差距不大，但实际跑起来差别惊人。我们写个测试程序，生成 10 万条随机数据分别排序。

void TestOP() {
    srand((unsigned int)time(NULL));
    const int N = 100000;
    int* a1 = (int*)malloc(sizeof(int) * N);
    int* a2 = (int*)malloc(sizeof(int) * N);
    for (int i = 0; i < N; ++i) {
        a1[i] = rand();
        a2[i] = a1[i];
    }
    int begin1 = clock();
    InsertSort(a1, N);
    int end1 = clock();
    int begin2 = clock();
    ShellSort(a2, N);
    int end2 = clock();
    printf("InsertSort:%d\n毫秒", end1 - begin1);
    printf("ShellSort:%d\n毫秒", end2 - begin2);
    free(a1);
    free(a2);
}

运行结果令人震惊：直接插入排序耗时约 0.6 秒，而希尔排序仅需 0.006 秒。如果数据量增加到 100 万，直接插入排序可能需要几十秒甚至更久，而希尔排序依然在 0.1 秒以内搞定。O(N^2) 的代价在大数据面前确实难以承受。

总结一下，直接插入排序适合小规模或基本有序的数据；而希尔排序通过预处理大幅提升了效率，是工程实践中值得掌握的经典算法。