一 希尔排序的原理
1.基本思想
2.希尔排序的优劣
逆序有序的数组排序时，时间复杂度为O ( n 2 ) O(n^2)O(n 2 )，此时效率最低。
顺序有序的数组排序时，时间复杂度为O ( n ) O(n)O(n)，此时效率最高。
我们发现，当被排序的对象越接近有序时，插入排序的效率越高，那我们是否有办法将数组变成接近有序后再用插入排序，此时希尔大佬就发现了这个排序算法，并命名为希尔排序。
二 希尔排序的动图演示
1.插入排序动图演示
2.希尔排序动图演示
三 代码实现
1.插入排序的实现
void insertsort(int* a, int n)
{
for (size_t i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end]>tmp)
{
a[end + 1] = a[end];
}
else
{
break;
}
end--;
}
a[end + 1] = tmp;
}
}
代码从第一个元素开始，不断使前i个元素变得有序
2.希尔排序的实现
void shellsort(int* a, 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 = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
希尔排序是对插入排序的优化，基本思路是先选定一个整数作为增量，把待排序文件中的所有数据分组，以每个距离的等差数列为一组，对每一组进行排序，然后将增量缩小，继续分组排序，重复上述动作，直到增量缩小为1时，排序完正好有序。
希尔排序原理是每一对分组进行排序后，整个数据就会更接近有序，当增量缩小为1时，就是插入排序，但是现在的数组非常接近有序，移动的数据很少，所以效率非常高，所以希尔排序又叫缩小增量排序。
每次排序让数组接近有序的过程叫做预排序，最后一次插入是直接插入排序。
而这个增量gap的选取，最初希尔提出的增量是 gap = n / 2，每一次排序完让增量减少一半gap = gap / 2，直到gap = 1时排序变成了直接插入排序。直到后来Knuth提出的gap = [gap / 3] + 1，每次排序让增量成为原来的三分之一，加一是防止gap <= 3时gap = gap / 3 = 0的发生，导致希尔增量最后不为1，无法完成插入排序。所以，可以根据自己的需要进行选取。
