对于直接插入排序：最好的情况（关键字在记录序列中顺序有序）：的次数：“移动”的次数：“比较”自N=n-1i-l最坏的情况（关键字在记录序列中逆序有序）：“比较”白的次数：“移动”的次数：1-1n-1(n-1)(n + 2)(n -1)(n + 2)(i+1) =(i+l) =222i=li=l11
11 对于直接插入排序： 最好的情况（关键字在记录序列中顺序有序）： “比较”的次数： 最坏的情况（关键字在记录序列中逆序有序）： “比较”的次数： 1 1 1 1 = − − = n n i 0 “移动”的次数： “移动”的次数： 2 1 2 1 1 1 (n )(n ) (i ) n i − + + = − = 2 1 2 1 1 1 (n )(n ) (i ) n i − + + = − =
10. 2. 2希尔排序希尔排序也是一种插入排序方法，实际上是一种分组插入方法。其基本思想是：先取定一个小于n的整数d作为第一个增量，把表的全部记录分成d个组，所有距离为d的倍数的记录放在同一个组中，在各组内进行直接插入排序；然后,取第二个增量d（<d),重复上述的分组和排序,直至所取的增量d,=1(d<d-I<...<d,<d,),即所有记录放在同一组中进行直接插入排序为止12
12 10.2.2 希尔排序 希尔排序也是一种插入排序方法,实际上是一种分组 插入方法。 其基本思想是：先取定一个小于n的整数d1作为第 一个增量,把表的全部记录分成d1个组,所有距离为d1 的倍数的记录放在同一个组中,在各组内进行直接插入 排序；然后,取第二个增量d2 (＜d1 ),重复上述的分组和 排序,直至所取的增量dt =1(dt<dt-1<.<d2<d1 ),即所有记 录放在同一组中进行直接插入排序为止
将记录序列分成若干子序列，分别对每个子序列进行插入排序。例如：将n个记录分成d个子序列：R[kd] }[R[0] ,R[d] .R[2d] . ... .(R[1] ,R[1+d] , R[1+2d] , ... , R[1+kd] ](R[d-1] R[2d-1] . R[3d-1] ...., R[(k+1)d-1] 3其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。13
13 将记录序列分成若干子序列，分别对每个子序列进行 插入排序。 其中，d 称为增量，它的值在排序过程中从大到小逐 渐缩小，直至最后一趟排序减为 1。 例如：将 n 个记录分成 d 个子序列： { R[0]， R[d]， R[2d]，.， R[kd] } { R[1]， R[1+d]， R[1+2d]，.，R[1+kd] } . { R[d-1]，R[2d-1]，R[3d-1]，.，R[(k+1)d-1] }
例如:916251230471123361831第一趟希尔排序，设增量d=51123|121816|2536|30|4731第二趟希尔排序，设增量d=39181213130473611/23/16/25第三趟希尔排序。设增量d=191112161823|25|30|31364714
14 例如： 16 25 12 30 47 11 23 36 9 18 31 第一趟希尔排序，设增量 d =5 11 23 12 9 18 16 25 36 30 47 31 第二趟希尔排序，设增量 d = 3 9 18 12 11 23 16 25 31 30 47 36 第三趟希尔排序，设增量 d = 1 9 11 12 16 18 23 25 30 31 36 47
/*希尔排序算法*void ShellSort(RecTypeRll,intn)inti,i,d;RecType temp;/*d取初值n/2*/d=n/2;while (d>0)for（i=d;i<n;i++)/*将R[d..n-1分别插入各组当前有序区*/{j-i-d;while(j>=0&&Rlil.key>R[j+dj.key)/*Rli]与R[i+d]交换*/temp-R[i];R[i]=Rj+d];R[j+d]=temp;j=j-d;/*递减增量d*/d=d/2;15
15 void ShellSort(RecType R[],int n) /*希尔排序算法*/ { int i,j,d;RecType temp; d=n/2; /*d取初值n/2*/ while (d>0) { for (i=d;i<n;i++) /*将R[d.n-1]分别插入各组当前有序区*/ { j=i-d; while (j>=0 && R[j].key>R[j+d].key) { temp=R[j]; /*R[j]与R[j+d]交换*/ R[j]=R[j+d];R[j+d]=temp; j=j-d; } } d=d/2; /*递减增量d*/ } }