排序算法(4)希尔排序

排序算法(4)希尔排序

原理:

  希尔排序也称缩小增量排序；希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序， 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时（用gap = gap / n+ 1 控制，越来越小，即增量减小），保证了最后一次进行直接插入排序，算法终止。

（其中直接插入排序是希尔排序gap = 1的特例）另外，gap越大，值越大的容易到最后面，但是不太接近有序。  一般gap不要超过数组大小的一半.

  你可能会说为什么一开始就直接插入排序，毕竟最后也要进行一次直接插入排序，这是因为希尔排序在数的数量很多时比直接插入快很多，毕竟将有序数组排序肯定比一大段无序数组排序快。我不会做动画，网上有动画，看一下更好理解

转载:希尔排序动画

代码实现:

void ShellSort(int arr[], int n)
{
	int gap = n;//gap是间隔
	while (gap > 1)
	{
		gap = gap / 3 + 1;//3是初始间隔,可以自定义，会越来越小，最终是1
		//单趟的直接插入排序
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int temp = arr[end + gap];
			//直接插入排序是end减1，这个是end减gap，是步进值
			for (; end >= 0 && arr[end] > temp; end -= gap)
			{
				arr[end + gap] = arr[end];
			}
			arr[end + gap] = temp;
		}
 
	}
}