【26】希尔排序

参考高爽的博客http://hi.baidu.com/gsgaoshuang/item/17a8ed3c24d9b1ba134b14c2

1. 希尔排序又称为缩小增量排序，属于插入排序算法的改进。

2. 对于插入排序算法来说，如果原来的数据就是有序的，那么数据就不需要移动，而插入排序算法的效率主要消耗在数据的移动中。因此可知：如果数据的本身就是有序的或者本身基本有序，那么效率就会得到提高。

3. 希尔排序的基本思想

   每次选择一个增量d，然后把间隔相同元素分成同一组。这样整个序列分成多个组，在组内进行插入排序。直到增量d等于0，整个序列已经排好序。

   第一次增量d为序列元素个数n的一半即n/2，之后每次d = d/2。

   希尔排序是不稳定的排序算法，虽然直接插入排序是稳定的排序算法，但是我们分成多个组进行插入排序可能导致稳定性发生变化所以是不稳定的排序算法。

4. 为什么希尔排序比基本的插入排序效率高呢？

   分析希尔排序的时间复杂度很困难，但是根据大量的实验统计资料得出，当n很大的时候利用希尔排序的时间复杂度大概在O(n^1.3)，比O(n^2)快了很多，所以比起一般的插入排序快

5. 举例：数组的长度为10，数组元素为：25,19,6,58,34,10,7,98,160,0

    （1）第一次选择增量d = n/2为5，则有

      则第一次利用增量d = 5排完序为 10 7 6 58 0 25 19 98 160 34

    （2）第二次选择增量d = d/2为2，则有

      则第二次利用增量d = 2排完序为 0 7 6 25 10 34 19 58 160 98

    （3）第三次选择增量d = d/2为1，则有

       则第三次利用增量d = 1排完序为 0 6 7 10 19 25 34 58 98 160

    （4）第四次d = 0，说明整个序列为有序序列

6. 示例代码

//希尔排序
void ShellSort(int *arrNum, int n){
	//不合法数据
	if(arrNum == NULL || n <= 0){
	   return;
	}
	//第一次选择增量d为n/2
	int d = n/2;
	while(d >= 1){
		//相差为d的元素是同一个序列直接用插入排序
		for(int i = d; i < n; i++){
			int tmp = arrNum[i];
			int j;
			for(j = i-d; j >= 0; j -= d){
				if(arrNum[j] > tmp){
				   arrNum[j+d] = arrNum[j];
				}
				else{
				   break;
				}
			}
			if(j != i-d){
			    arrNum[j+d] = tmp;
			}
		}
		//增量减半
		d >>= 1;
	}
}