用C语言实现希尔排序算法

这是C语言学习的第49篇文章。

希尔排序是十大排序算法之一，今天，我们来一起揭开希尔排序的神秘面纱。

这篇文章将完全从零开始，力求用最生活化的语言让你彻底理解它。

希尔排序：给插入排序装上“火箭推进器”

想象一下，你有一副杂乱无章的扑克牌。现在让你用一种方法把它整理成从小到大的顺序，你会怎么做？

很多人会使用一种叫做 “插入排序” 的方法：

拿起第一张牌，它本身就是有序的。

拿起第二张牌，和第一张比较，插到它前面或后面。

拿起第三张牌，在已经排好序的前两张牌中，找到合适的位置插进去。

重复这个过程，直到所有牌都插入到正确的位置。

这种方法简单直观，但对于一副混乱的牌，你需要不断地在已排序的部分中寻找插入位置，并进行大量的“移动”操作，效率比较低。

就像把一个一个的零件，慢慢地塞进一个已经组装了一半的机器里，非常费劲。

那么，有没有办法能让这个“插入”的过程更快一些呢？

答案是肯定的！这就是希尔排序的天才之处。

核心思路：化整为零，先粗后精

希尔排序的核心思想非常朴素：如果整个序列是基本有序的，那么插入排序的效率会非常高。

“基本有序”是什么意思？就是说，虽然序列不是完全整齐的，但大部分元素都已经在它最终该在的位置附近了，不需要进行长距离的移动。

如何让一个混乱的序列变得“基本有序”呢？

希尔排序的发明者Donald Shell想出了一个绝妙的主意：不要一个个地比，我们先把整个队伍打散，进行几次“远距离”的整理，让元素先大踏步地回归到自己的区域，然后再进行精细的微调。

这个“打散”和“远距离整理”的工具，就是 “增量”（Gap）。

逻辑思路：一步一步看得懂

让我们用一个具体的例子来模拟。假设我们要排序的数组是：[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]。

第1步：选择一个初始增量（Gap）

增量就是一个步长。我们第一次选择一个比较大的增量，比如 gap = 5。这意味着我们把整个数组分成5组：

第1组: 8, 3 (索引0, 5)

第2组: 9, 5 (索引1, 6)

第3组: 1, 4 (索引2, 7)

第4组: 7, 6 (索引3, 8)

第5组: 2, 0 (索引4, 9)

你看，我们不再是看相邻的元素，而是每隔5个位置取一个元素，组成一组。

第2步：对每一组进行插入排序

现在，我们对这5个小组分别进行我们前面提到的插入排序。

排序第1组 [8, 3] -> [3, 8]

排序第2组 [9, 5] -> [5, 9]

排序第3组 [1, 4] -> [1, 4] (已经有序)

排序第4组 [7, 6] -> [6, 7]

排序第5组 [2, 0] -> [0, 2]

现在，整个数组变成了：[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]。

是不是看起来还是很乱？但请仔细感受：相比于最初的 [8, 9, 1, 7, 2, ...]，现在小的数字（如0, 1, 2, 3）已经更多地出现在左边，大的数字（如7, 8, 9）更多地出现在右边了。它已经 “基本有序” 了！

第3步：缩小增量（Gap），继续分组排序

接下来，我们把增量缩小，比如缩小一半，gap = 2。现在我们把数组分成2组：

第1组: 3, 1, 0, 9, 7 (索引0, 2, 4, 6, 8)

第2组: 5, 6, 8, 4, 2 (索引1, 3, 5, 7, 9)

再次对这两组分别进行插入排序：

排序第1组 [3, 1, 0, 9, 7] -> [0, 1, 3, 7, 9]

排序第2组 [5, 6, 8, 4, 2] -> [2, 4, 5, 6, 8]

现在，整个数组变成了：[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]。

哇！是不是整齐多了？已经非常接近最终结果了。

第4步：最后一遍精细调整（标准插入排序）

最后，我们把增量设为1，gap = 1。这意味着什么？意味着我们把整个数组当成一组，进行一次标准的插入排序。

此时，数组是 [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]，已经非常有序了。插入排序对于这种近乎有序的数组，效率极高，只需要进行很少的几次比较和移动，就能迅速完成排序。

最终结果：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]。

总结一下希尔排序的精髓：

通过一个由大到小变化的增量（Gap），将整个序列分割成若干子序列，分别进行插入排序。随着增量的不断缩小，整个序列变得越来越有序。当增量为1时，整个序列已经“基本有序”，此时再进行最后一次插入排序，就能以极高的效率完成任务。

它就像先用大网眼的筛子把大鱼和小鱼大致分开，再用中网眼的筛子进一步分离，最后用小网眼的筛子做精细分离。每一步都为下一步创造了更好的条件。

C语言实现代码

理解了上面的思路，代码就非常清晰了。这里我们使用一个经典的增量序列：初始增量为数组长度的一半，然后每次减半，直到1。

#include <stdio.h>

// 希尔排序函数

void shellSort(int arr[], int n) {

// 初始增量gap为数组长度的一半，然后每次减半

for (int gap = n / 2; gap > 0; gap /= 2) {

// 从第gap个元素开始，对每一个分组进行插入排序

// 注意：这里i++，意味着我们是依次在各个分组之间“轮流”处理一个元素

// 而不是完全处理完一个分组再处理下一个，但效果是一样的，且代码更简洁。

for (int i = gap; i < n; i++) {

// 下面就是标准的插入排序逻辑，但比较和移动的步长是gap，而不是1

int temp = arr[i]; // 当前待插入的元素

int j;

// 在同一个分组内（步长为gap），寻找temp的插入位置

// 将比temp大的元素都向后移动gap个位置

for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {

arr[j] = arr[j - gap];

}

// 将temp插入到正确位置

arr[j] = temp;

}

}

}

// 一个打印数组的辅助函数

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++) {

printf("%d ", arr[i]);

}

printf("\n");

}

// 主函数，测试希尔排序

int main() {

int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};

int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度

printf("排序前的数组: \n");

printArray(arr, n);

shellSort(arr, n); // 调用希尔排序函数

printf("排序后的数组: \n");

printArray(arr, n);

return 0;

}

代码关键点解释：

外层循环 for (int gap = n / 2; gap > 0; gap /= 2)：

控制增量的变化，从n/2开始，每次减半，直到1。

中层循环 for (int i = gap; i < n; i++)：

这个循环非常巧妙。它从gap开始，遍历数组。i指向的是每个分组中“未排序部分”的第一个元素。通过i++，我们实际上是轮流处理不同分组的下一个待排序元素，而不是一次性处理完一个分组。这样做代码更简洁，效果等同于分别处理每个分组。

内层循环 for (j = i; ...; j -= gap)：

这是分组内的插入排序核心。它从当前位置i开始，以gap为步长向前比较。如果前面的元素比temp大，就把它向后移动gap个位置。循环直到找到temp应该插入的位置。

希望这篇超过1000字的详细解释，能让你对希尔排序有一个清晰而深刻的认识！

它是对简单插入排序的一次伟大改进，体现了“逐步求精”的深刻思想。

后记

不知不觉间，C语言入门的系列文章写了49篇，感谢各位小伙伴，在这个短视频大行其道的时代，还有这么多人来看这些枯燥的文字，我真的很感动。

易经里说“七日来复”，七七四十九，正是一个完整的循环。

相信你通过这49篇内容的学习，对C语言的核心知识点已经有了一个较为清晰的认识。

如果能帮到你，我感到很高兴。

各位伙伴有什么需求，或者学习C语言的道路上遇到什么困难，都可以问我。

至此，C语言系列将暂告一段落，接下来我计划推出一个关于“AI视频制作技术”的新专栏，欢迎各位继续关注与支持！