目录
一、基本思想
1.1 引入希尔排序的原因
为什么要引入希尔排序呢？
因为直接插入排序的缺点就是怕逆序，如果待排的序列是逆序的情况，那么效率将直接下降，而希尔排序就是对直接插入排序的一个优化。
那什么是希尔排序呢？
1.2 基本思想
希尔排序法又称缩小增量法。希尔排序法的基本思想是：
将待排序的序列划分成若干个子序列（也就是若干组），分别进行插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。
通俗来讲，希尔排序分为两步：
- 预排序（目的：让数组接近有序）
- 直接插入排序
二、思路分析
我们清楚直接插入排序是如何实现的，那预排序是如何实现的呢？
接下来我们结合图来详细讲解一下希尔排序中预排序的过程：
这里以升序为例：
预排序完成之后，一组，二组，三组分别都是一组有序的序列，
虽然没有达成整个序列的有序，但相比之前，更加接近有序。
在此基础上，进行直接插入排序，会比之前更快，
之前的9需要移动n次，而现在的9只需要移动3次，因为每跳一次，步长为3，跳的更远了，所以移动的速度也就更快了。
所以说，预排序针对逆序情况特别凸显它的效率高效。
三、gap分组问题
预排序到底排几次比较合适，gap分为几组才是最恰当的呢？
我们知道:
gap越大，我们期望它可以跳的越快。大的数据就可以越快的跳到后面，小的数据也就可以越快的跳到前面。
当然，整个序列也就越不接近有序。
gap越小，它就跳的越慢，整个序列也就越接近有序。
当gap>1的时候，是预排序
当gap==1的时候，就是直接插入排序。
gap的取值方式有很多种，研究发现，gap=gap/3;是相对比较合理的，但是除以3并不能保证最后一次gap==1（也就是无法进行直接插入排序，因为希尔排序=预排序+直接插入排序）
所以，gap=gap/3+1；就可以保证最后一次gap一定等于1，也就是可以进行直接插入排序。
当然我们也可以选择gap=gap/2，但最好还是使用gap=gap/3+1。
四、代码实现
4.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 (int j = 0; j < gap; j++)
{
//完成一组的排序
for (int 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;
}
}
}
}
4.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;
}
}
}
五、易错提醒
提醒一
代码一和代码二是两种执行次序，具体执行步骤如下所示：
代码一
代码二
代码一和代码二在效率执行上并没有任何区别，因为它们完成的是同一个过程。
提醒二
注意临界问题，for循环里i<n-gap的原因：
六、时间复杂度分析
希尔排序的平均时间复杂度是：O(N^1.3)
为什么呢？
我们可以进行一下简单的推导：
一共有gap组数据，gap=gap/3+1，这里假设忽略掉+1（目的是为了方便计算），变成gap=gap/3，
那么每组就有3个数据，因为每组数据个数=n/gap（n为数据总数）
例：下图n=12，共有12个数据，每组有3个数据，所以共分了4组，也就是gap=n/3=4.
这里千万不要混淆gap组的意思，根据图来进行理解
我们知道，一趟预排序的消耗次数=每组的比较次数*组数
所以，
第一趟预排序消耗的次数（最坏情况下）：（1+2）*n/3=n
（因为gap=gap/3=n/3，所以每组3个数据）
1表示：一组序列的第二个元素最坏比较多少次
2表示：一组序列的第三个元素最坏比较多少次
n/3表示：一共有多少组
第二趟预排序消耗的次数（最坏情况下）：(1+2+3+......+8)*n/9=9*8/2*n/9=4n
（因为gap=gap/3=n/3/3=n/9，所以每组9个数据）
依次类推......
这里需要注意的是：
当进行了第一趟最坏情况下的预排之后，第二趟不一定最坏了，因为第一趟预排序对第二趟预排有一定的影响。
严格来说第二趟到不了最坏的情况，它应该比4n要小，那具体是多少，就很难算出来，这里涉及复变函数，概率等知识的运用。
所以说到最后一趟，也就是当gap==1时，就是直接插入排序
此时的序列已经非常接近有序了。
所以，
最后一趟预排序消耗次数（正常情况下）：n
这里可以用函数关系图来表示希尔排序比较次数和gap之间的关系：
从图中我们可以看出他们之间大致关系如上所示，经推算希尔排序的平均时间复杂度为：O(N^1.3)
这里我们也可以用另一种方式来求解时间复杂度。
可以计算一下走了多少趟预排序，也就是gap变化了几次，外层while循环走了多少次？
分析如下图所示：
所以研究希尔排序的最好时间复杂度是没有任何意义的。
提醒：
- 希尔排序的时间复杂度不好计算，因为gap取值方式的不同，会对排序效率有直接影响，这就导致了希尔排序的时间复杂度计算变得复杂，很难给出一个确切的复杂度，因此很多资料中希尔排序的时间复杂度都不固定。
- 我们上述分析的是按照Knuth提出的方式取值的，而Knuth进行了大量试验统计资料得出，当n很大时，关键码平均比较次数和对象平均移动次数大约在 O(n^1.25)到 O(1.6n^1.25)范围内。
故，我们直接按照O(N^1.3) 来计算即可。
七、排序小tips
我们在进行任何排序都要先处理好单趟的问题，然后再考虑整体，这样可以使我们写代码的思路更加清晰明了，也更容易写出正确高效的代码。