排序算法---希尔排序

1、如何进行希尔排序

希尔排序是直接插入排序的优化，具体实现是先进行以gap间隔分别进行排序，将数组排成快要接近有序，最后一次gap为1的排序，实际上是直接插入排序，因为直接插入排序在接近有序时时间复杂度最小，所以以此进行优化，gap大于1的排序称为预排序。

2、程序

void ShellSort(int* a,size_t size)
{
	assert(a);
	int gap = size;
	while(gap>1)
	{
		gap = gap/3+1;//保证最后一次gap为1
		//多路排序并行
		for(int i = 0; i < size-gap; i++)
	  {
		int end = i;
	    int tmp = a[end + gap];
	    while(end >= 0 && tmp < a[end])//间距为gap的插入排序
	    {
		   a[end+gap] = a[end];
		   end -= gap;
	    }
	    a[end+gap] = tmp;
	  }
	}	
}

3、时间复杂度

时间复杂度在O(N)和O(N*N)之间，大概是O(N^1.25 - 1.6N^1.25)。在初始数组数据已经接近有序时，优化效率最低。