1.简介

在插入排序中，在待排序序列的记录个数比较少，而且基本有序，则排序的效率较高。

1959 年，Donald Shell 从“减少记录个数” 和 “基本有序” 两个方面对直接插入排序进行了改进，提出了希尔排序算法。

希尔排序又称为缩小增量排序。即将待排序记录按下标的一定增量分组（减少记录个数），对每组记录使用直接插入排序算法排序（达到基本有序）；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1，整个序列基本有序，再对全部记录进行一次直接插入排序。

2.算法思想

希尔排序是一种高效的排序算法，基于插入排序算法。这种算法避免了插入排序中的大量移动，如果较小的值在最右边，就必须移到最左边。较小的值在最右边，必须移到最左边。

3.算法步骤：

设待排序的记录存储在数组 x[1...n] 中，增量序列为 {$g_1, g_2, ..., g_t$}, $g_1>g_2>...>g_t$=1 。

第一趟增量 $g_1$, 所有间隔为 $g_1$ 的记录分在一组，对每组记录进行插入排序。

第二趟取增量 $g_2$，所有间隔为 $g_2$ 的记录分在一组，对每组记录进行插入排序。

依次进行下去，直到所取增量 $g_t$ = 1，所有记录在一组中进行插入排序。

4.图解

假设要对 7 4 3 5 2 1 6 这 7 个数字进行排序。

1. 第一轮排序的示意图（gap=3）

2. 第二轮排序的示意图（gap=2）

3. 第三轮排序的示意图（gap=1）

5.代码模板

一般来说对希尔排序不需要了解到这么细，看懂上面的图解就可以了。只有那些对排序算法的细节感兴趣的同学才需要看下面的代码。

#include<bits/stdc++.h>
using namespace std;
int x[10001];
int main(){
    int n,tmp;
    cin>>n;

    for(int i=1;i<=n;i++)
		cin>>x[i]; //数字输入到 x 数组 ,一开始是无序的 

	for(int gap=n/2;gap>0;gap=gap/2)
	{
		for(int i=1;i<=gap;i++) //有 gap 个系列 
		{
			//对 x[i],x[i+gap],x[i+2gap]....排序，下面的这两层循环用插入排序的思想 
			for(int j=i+gap;j<=n;j+=gap)
			{
				tmp = x[j];
				int k;
				for(k=j-gap;k>0;k-=gap) // x[i], x[i+gap], ....x[j] 已经有序 
				{
					if(x[k]>tmp) x[k+gap] = x[k];
					else break;
				}
				x[k+gap] = tmp;
			}
		}

	}
 
	for(int i=1;i<=n;i++) //输出有序的数字 
		cout<<x[i]<<" "; 
 
    return 0;
}