希尔排序是对直接插入排序的一种改进算法。它基于插入排序的两个性质：

（1）若待排序记录按关键字基本有序，直接插入排序效率很高

（2）若带排记录个数较少，直接插入排序效率很高

希尔排序的基本思想：一个数组有n个数据，把所有数据以间距m分组，分成n/m个组,间距为m的数据为一组数据；例如有10个数据，以间距5分组，a[0],a[5]为一组；a[1],a[6]为一组；...a[4],a[9]为一组，每组数据进行插入排序。然后缩小间距，进行排序。直到间距为1，所有数据变为有序数据。间距选取不唯一。在下面实例中，我们第一次取间距为n/2，每次减半，直到为1；

平均情况的时间复杂度          最好情况的时间复杂度               最坏情况的时间复杂度         空间复杂度

 O(nlog2(n))~O(n^2)                    O(n^1.3)                                  O(n^2)                        O(1)

#include<iostream>
using namespace std;
template<class Type>
void ShellSort(Type a[],int n)//希尔排序
{
	for(int d=n/2;d>=1;d=d/2)
	{
		for(int i=d;i<n;i++)
		{
			Type tem=a[i];
			int j;
			for(j=i-d;j>=0&&tem<a[j];j=j-d)
			a[j+d]=a[j];
			a[j+d]=tem;
		}
	}	
 } 
 int main()
 {
    int a[7]={49,27,65,97,76,13,38};
	for(int i=0;i<7;i++)
	cout<<a[i]<<" ";
	cout<<endl;
	ShellSort(a,7);
	for(int i=0;i<7;i++)
	cout<<a[i]<<" ";
	cout<<endl;
	return 0;
 }