在学习希尔排序前，请先学习插入排序（直接插入排序），传送门：直接插入排序
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
希尔排序是基于插入排序的以下两点性质而改进的：
1. 对几乎已经排好序的数据操作时，效率高。
2. 对记录数少的数据操作时，效率高。
算法步骤：
1. 原始数组 a[10] = {5, 2, 6, 1, 3, 9, 10, 7, 4, 8}。
2. 初始增量gap = length/2 = 10/2 = 5，数组被分成5组：[5, 9]，[2, 10]，[6, 7]，[1, 4]，[3, 8]。
对这5组分别进行插入排序[5, 9]，[2, 10]，[6, 7]，[1, 4]，[3, 8]，排序完后数组为：{5, 2, 6, 1, 3, 9, 10, 7, 4, 8}（可以看出没有变动，原因是原数组拆分后，各组已是有序的）。
3. 然后缩小增量，gap = 5/2 = 2，数组被分成两组[5, 6, 3, 10, 4]，[2, 1, 9, 7, 8]。
对以上两组分别再进行插入排序[3, 4, 5, 6, 10]，[1, 2, 7, 8, 9]，排序完后数组为：{3, 1, 4, 2, 5, 7, 6, 8, 10, 9}。
4. 然后再缩小增量gap = 2/2 = 1，此时整个数组为一组[3, 1, 4, 2, 5, 7, 6, 8, 10, 9]。
对其进行插入排序后，数组为：{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
演示如图：
接下来就是使用代码优雅的表示出来。
完整代码：
#include <stdio.h>
#include <stdlib.h>
void ShellSort(int arr[], int len)
{
int i, end, tmp;
int gap = len;
do
{
gap/=2; // 计算出组数（组数=元素在数组中的跨度）
// 使用直接排序法对每组数据进行排序
for (end=gap; end<len; end+=gap)
{
if(arr[end-gap]>arr[end])
{
tmp = arr[end];
for(i=end-gap; arr[i]>tmp ; i-=gap)
{
arr[i+gap] = arr[i];
}
arr[i+gap] = tmp;
}
}
}while(gap>1);
}
int main()
{
int i, a[10] = {5, 2, 6, 1, 3, 9, 10, 7, 4, 8};
ShellSort(a, 10);
printf("排序后的结果是：");
for(i=0; i<10; i++)
{
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
希尔排序算法中的"gap"（间隔）是什么？
"gap"（间隔）是指对待排序的元素进行分组的步长或间隔。希尔排序通过将整个待排序序列分割成多个子序列来进行排序，每个子序列包含相隔一定间隔的元素。
一、 为什么gap=length/2，而不是/3、/4等?
在希尔排序算法中，间隔序列的选择会直接影响排序的性能和效率。通常情况下，希尔增量序列（Shell's original gap sequence）采用的是 gap/2 的方式。
从理论上来说，任何大于1的间隔序列都可以用于希尔排序。但是，更好的间隔序列应该具有一些特点，比如：
1. 序列中的各个元素应该互质（确保每个分组中的元素不会被重复地排到同一个子序列中）。
2. gap的最后值应该为1（确保最后一次排序时，整个序列会被进行一次完整的插入排序）。
3. 序列的长度应该尽可能短，这样可以减少排序过程中的比较次数和交换次数。
希尔增量序列恰好满足以上三个条件，并且经过实验验证，使用 gap/2 的方式可以获得比较好的排序效果。相比之下，使用 gap/3 或其他较大的间隔序列可能会导致排 序效率下降，因为这些序列可能不满足上述的条件，导致分组和排序不够均匀，影响了排序的性能。
二、 为什么使用"gap"（间隔）来分组，不使用连续的元素来分组？
当我们使用连续的分组时，比如每次比较相邻的两个元素，这种方法在某些情况下可能会导致元素的移动距离较大，从而增加了排序的时间复杂度。
而使用间隔分组的方式，可以让较小的元素通过交换位置向前迅速移动，从而减少逆序对的数量。通过不断缩小间隔，最终达到间隔为1的情况，此时只需要进行简单的插入排序 即可完成排序，而插入排序对几乎有序的数据表现良好。