目录
一.希尔排序
1.1希尔排序的原理
1.2希尔排序的代码思路
1.3希尔排序的代码实现
1.1希尔排序的原理
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
希尔排序大体上可以分为两步：
1.预排序
2.插入排序
为什么要增加预排序这一步呢？
我们知道插入排序再排逆序的数组时时间复杂度为最坏的情况。所以我们才要进行预排序，预排序的目的是为了让数组接近有序。当数组接近有序时使用插入排序也就绰绰有余了。
让我们先来看第一步：
1.预排序
我们知道插入排序再排逆序的数组时时间复杂度为最坏的情况。所以我们才要进行预排序。
预排序的目的是为了让数组接近有序，简而言之预排序就是将大的数调到后面，小的数调到前面。
预排序中我们要引入分组的概念，要用到gap（间隔），让我们用画图理解：
当gap为3的时候，就是从数组的第1个数开始，找到第4个数，也就是和他间隔为3的数，再从第4个数找与它间隔为3的数，以此类推，直到数组的最后一个数，或者超出数组的范围。
2.插入排序
对插入排序有疑问的小伙伴可以看我的另一篇博客：直接插入排序。
这里我就不再过多赘述了。
1.2希尔排序的代码思路
让我来看单趟预排序的代码实现以及思路：
int gap = 3;
for (size_t i = 0; i < n-gap; i += gap)
{
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;
}这段代码就是对数组的第一个数，取间隔为gap所形成的预排序。
让我们将这段代码和插入排序的比较一下：
void InsertSort(int* a, int n)
{
// [0, n-1]
for (int i = 0; i < n - 1; i++)
{
// [0, n-2]是最后一组
// [0,end]有序 end+1位置的值插入[0,end]，保持有序
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
我们会发现，这直接插入排序不就是单趟预排序的gap变成了1嘛。
换而言之，直接插入排序就是gap为一的预排序。
预排序的完整代码如下：
int gap = 3;
for (int j = 0; j < gap; j++)
{
for (size_t i = j; i < n - gap; i += gap
{
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;
}
}
}当j为0时，预排的是红色的一组。
当j为1时，预排的是绿色的一组。
当j为2时，预排的是紫色的一组。
1.3希尔排序的代码实现
思路讲完了，预排序也讲完了。希尔排序终于要来了。在现实情况下，我们能知道gap为多少吗？像前面我的只排6个数据，gap=3还是可以的，但是如果我们要排一百万，一千万，一亿甚至更多的数呢？gap又要怎么算呢？我们要知道。gap越小预排序越接近有序，但也排的越慢。gap越大，预排序越不接近有序，但排的越快。但是我们找不到gap应该取多少，所以我们可以让gap等于一个随机的数但要越来越小直到gap=1进行插入排序。
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
// +1保证最后一个gap一定是1
// gap > 1时是预排序
// gap == 1时是插入排序
gap = gap / 3 + 1;
for (size_t 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;
}
}
}