引言

希尔排序又称缩小增量排序,它是根据直接插入算法更适用于基本有序的排序表和数据量不大的排序表这个特点(本身时间复杂度为n^2的算法若是用在“正序”序列中复杂度可提高到n)对直接插入排序进行改进而得来的。
我想了一下午,也没有想到和在现实生活中应用到希尔排序的动作,可能是因为虽然其效率高,但是比起直接插入排序要麻烦许多,所以在现实中的应用很少,当然了也有可能在现实中确实有,只是我并不晓得哈哈。
……
但是现实中没有,我们仍然可以通过自己的想象去捏造一个与之思想相同的场景去辅助我们理解。这里留给读者自行想象,就不给出具体引例了,取而代之的我们给出一个练习,帮助大家巩固:假如你还是在打牌,每人摸13张牌,好了就对这13个数,你使用希尔排序按照下面的代码思想走一趟吧!(tip:第一次选的增量是13/2(取下界)=6,所以第一波的分组有:1,7,13;2,8;3,9;4,10;5,11;6,12。你选对了吗(〃'▽'〃)?

代码实现

void ShellSort(Elemtype A[],int n){
	/*执行完一趟目前增量的排序后,按照希尔的建议(每次缩小一倍)缩小
增量直到最后增量为1,即对所有的元素进行一次直接插入排序*/
	for(dk=n/2;dk>=1;dk=dk/2){	
		/*对于该增量情况下的所有分组均在这一个for循环中完成直接插
入排序,所以每次i只加1*/
		for(i=dk+1;i<=n;++i){
			/*一个分组中前面大,后面小了,需要将A[i]插入有序增量子表*/
			if(A[i]<A[i-dk]){
				A[0]=A[i];	
				//直接插入排序中的后移及插入
				for(j=i-dk;j>0&&A[0]<A[j];j-=dk)
					A[j+dk]=A[j];
				A[j+dk] = A[0];
			}
		}
	}
}