4、C语言程序 void ShellSort(Data Type all, int n, int dd int numofD) i int i,j,k, m,span Data lype temp for(m=0; m numOfD; m++i span =d[m] for(k=0; k< span; k++) for(i =k; i< n-span; i=i+span) temp=ai+span];j=i while >-1&& temp. key <=all key)i alj+span]=ali J-span aLj+span=temp;
11 4、C语言程序 void ShellSort(DataType a[], int n, int d[], int numOfD) { int i, j, k, m, span; DataType temp; for(m = 0; m < numOfD; m++) { span = d[m]; 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.key <= a[j].key) { a[j+span] = a[j]; j = j-span; } a[j+span] = temp; } } } }
练习: 1.欲将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的关键码 按字母升序重排,则初始步长为的希尔排序一趟的结果是? 答:原始序列:Q,H,C,Y,P,A,M,S,R,D,F,X she-趟后: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 希尔排序 第趟256,301,0764863,742,5 d=5 第2趟 076,301 256,438。742.7518937 d=3 第[076,129,2356,301,4388694,722,751,863,93 d=1
12 练习： 1. 欲将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码 按字母升序重排，则初始步长为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