例2：设待排序的序列中有12个记录，它们的关键字序列T=(65，34，25，87，12，38，56，46，14，77，92，23） ，请写出希尔排序的具体实现过程。第1趟(d=6)254623653487123856147792234687923856141265253477(a)
例2：设待排序的序列中有12个记录，它们的关键字序列 T=(65， 34，25，87，12，38，56，46，14，77，92，23），请写出 希尔排序的具体实现过程。 第1趟 (d=6)
第2趟(d=3)141265462556347723879238143477462556126523879238(b)第3趟(d=1)143446561265237725879238121423253438465665778792(c)
第2趟 (d=3) 第3趟 (d=1)
public staticvoid sheliSort(int a, intI d, int numOfD)inti,j,k, m, span;int temp;int n = a.Length;for(m=0;m<numOfD;m++)//共numOfD次循环//取本次的增量值span = d[m];//共span个小组for(k= 0; k< span; k ++)for(i=k;i< n-span;i=i+ span)temp = a[i+span];j=i;while(j> -1 && temp< a[jD)a[i + span] = a[j];j=j- span;a[j + span]= temp;7M
public static void shellSort(int[] a, int[] d, int numOfD){ int i, j, k, m, span; int temp; int n = a.Length; for(m = 0; m < numOfD; m ++){ //共numOfD次循环 span = d[m]; //取本次的增量值 for(k = 0; k < span; k ++){ //共span个小组 for(i = k; i < n-span; i = i + span){ temp = a[i+span]; j = i; while(j > -1 && temp < a[j]){ a[j + span] = a[j]; j = j - span; } a[j + span] = temp; } } } }
算法分析：开始时的值较大，子序列中的对象较少排序速度较快；随着排序进展，d值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数记录已基本有序，所以排序速度仍然很快。时间效率：O(n(log2n))空间效率：0（1）一因为仅占用1个缓冲单元算法的稳定性：不稳定
算法分析：开始时d 的值较大，子序列中的对象较少， 排序速度较快；随着排序进展，d 值逐渐变小， 子序列中对象个数逐渐变多，由于前面工作的 基础，大多数记录已基本有序，所以排序速度 仍然很快。 时间效率：O(n(log2n)2 ) 空间效率：O（1）——因为仅占用1个缓冲单元 算法的稳定性：不稳定
练习：1.欲将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母升序重排，则初始d为4的希尔排序一趟的结果是？答：原始序列：Q,H,C,Y,P,A,M,S,R,D,E, Xshell趟后: P, A, C, S, Q,D, F, X,R, H, M, Y2.以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行希尔排序（取d=5,3,1）算法的各趟排序结束时，关键字序列的状态。解：原始序列：256，301，751，129，937，863，742，694，076，438希尔排序第1趟256,301，694,076，438，863，742,751，129，937d=5第2076,301，129,256,438,694，742,751,863,937d=3第3076,129,256,301,438,694,742,751,863,937d=1
练习： 1. 欲将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码 按字母升序重排，则初始d为4的希尔排序一趟的结果是？ 答： 原始序列： Q, H, C, Y, P, A, M, S, R, D, F, X shell一趟后： P, A, C, S, Q,D, F, X ,R, H, M, Y 2. 以关键字序列（256，301，751，129，937，863，742， 694，076，438）为例，写出执行希尔排序（取d=5,3,1）算 法的各趟排序结束时，关键字序列的状态。 解：原始序列: 256，301，751，129，937，863，742，694，076，438 第1趟 d=5 第2趟 d=3 第3趟 d=1 256，301，694，076，438，863，742，751，129，937 076，301，129，256，438，694，742，751，863，937 076，129，256，301，438，694，742，751，863，937