【初探数据结构】直接插入排序与希尔排序详解

我想吃余

发布于 2025-03-31 18:21:09

4570

文章被收录于专栏：数据结构初阶数据结构初阶 C语言学习

1. 直接插入排序

算法原理

插入排序是一种简单直观的排序算法，核心思想是：将数组分为“已排序”和“未排序”两部分。每次从未排序部分取出第一个元素，将其插入到已排序部分的正确位置，直到所有元素有序。

实际中我们玩扑克牌时，就用了插入排序的思想

步骤：

从第二个元素开始（假设第一个元素已排序）。
将当前元素与已排序部分的元素从后向前比较。
若当前元素更小，则将已排序元素后移，直到找到合适位置插入。

这个图可以帮助我们更好地理解这个逻辑：

代码解析

void InsertSort(int* a, int n) {
	//从第二个元素开始
    for (int i = 1; i < n; i++) {
        int end = i - 1;
        int tmp = a[i];
        //2.依次比较
        while (end >= 0) {
            if (tmp < a[end]) {
                a[end + 1] = a[end];
                end--;
            } else break;
        }
        //3.插入
        a[end + 1] = tmp;
    }
}

外层循环：从 i=1 第二个元素开始遍历所有元素。
内层循环：将 a[i] 插入到已排序区间 [0, i-1] 的合适位置。

时间复杂度

最好情况（已有序）：O(n)
最坏/平均情况：O(n²)

优缺点

优点：简单、稳定，适合小数据或部分有序数据。
缺点：大规模数据效率低。

2. 希尔排序

希尔排序是对直接插入排序的优化

算法原理（预排序+插入排序）

希尔排序是插入排序的改进版，通过“分组插入排序”减少元素移动次数。其核心思想是：将数组按间隔 gap 分组，对每组进行插入排序，随后逐步缩小 gap 直至为 1，最终进行一次全数组插入排序。

当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

代码解析

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

间隔序列：gap = gap / 3 + 1 确保最终 gap=1，进行最后一次完整插入排序。
分组插入：每组元素间隔为 gap，通过插入排序调整位置。

时间复杂度

希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好多书中给出的希尔排序的时间复杂度都是不固定的。

大多数参考资料提出：

平均情况：O(n^1.3)（取决于间隔序列）
最坏情况：O(n²)

优缺点

优点：比插入排序高效，适合中等规模数据。
缺点：不稳定，间隔序列的选择影响性能。

3. 对比与适用场景

特性	插入排序	希尔排序
时间复杂度	O(n²)	O(n^1.3) ~ O(n²)
空间	O(1)	O(1)
适用场景	小数据或部分有序	中等规模数据

4. 测试与示例

测试代码

// 插入排序测试
void TestInsertSort() {
    int a[] = {9,8,7,6,5,4,3,2,1,0};
    InsertSort(a, sizeof(a)/sizeof(int));
    PrintSort(a, sizeof(a)/sizeof(int)); 
    // 输出：0 1 2 3 4 5 6 7 8 9
}

// 希尔排序测试
void TestShellSort() {
    int a[] = {9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9};
    ShellSort(a, sizeof(a)/sizeof(int));
    PrintSort(a, sizeof(a)/sizeof(int)); 
    // 输出：-9 -8 -7 ... 7 8 9
}