在分析插入排序(插入排序算法实现)的算法性能的过程时知道。当数组规模较小或者存在较多的有序子序列时。插入排序将会在非常短的时间内完毕数组的排序，为此能够设计一个单调序列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;

	}

}

算法分析：从上述算法的实现过程中能够看出。希尔排序主要是先将数组分成若干个小的数组组成，然后对这些小的数组依次进行插入排序，经过这番排序之后，整个数组将会存在多个局部有序的子序列。这种数组再使用(h=1时)插入排序，将会非常快的完毕数组的排序。