在分析插入排序的算法性能的过程时知道，当数组规模较小或者存在较多的有序子序列时，插入排序将会在很短的时间内完成数组的排序，为此可以设计一个单调序列h[n]，将数组分为多个小的序列，然后这些小的序列使用插入排序。h[n]={1,4,7,10,13,16,19……，3*x+1}。

算法实现：

void sort::shell_sort(int* a, const int n)
{
	int h = 0;
	while (h<n/3)
		h = 3*h + 1;
	while(h>=1)
	{
		for(int i=h; i<n; i++)
		{
			for(int j=i; j>=h && a[j] < a[j-h]; j = j-h)
			{
				swap(a,j,j-h);
			}
		}
		h = h/3;
	}
}

算法----希尔排序（shell sort）