public void InsertsortO/对R0.n-1按递增有序进行直接插入排序 int i,j; RecType tmp; for(i=l;i< length;i++)∥直接插入排序是从第二个元素即R[开始的 tmp=R: /取出无序区的第一个元素 从右向左在有序区R|0.1中找R的插入位置 while (j>=0 & rljkey>tmp. key Rj+1}=R[jl;将关键字大于 tmp. key的元素后移 J--3 /续向前比较 RIj+1=tmp; /在j计+1处插入R
public void InsertSort() //对R[0..n-1]按递增有序进行直接插入排序 { int i,j; RecType tmp; for (i=1;i<length;i++) //直接插入排序是从第二个元素即R[1]开始的 { tmp=R[i]; //取出无序区的第一个元素 j=i-1; //从右向左在有序区R[0..i-1]中找R[i]的插入位置 while (j>=0 && R[j].key>tmp.key) { R[j+1]=R[j]; //将关键字大于tmp.key的元素后移 j--; //继续向前比较 } R[j+1]=tmp; //在j+1处插入R[i] } }
对于直接插入排序: 最好的情况(关键字在记录序列中顺序有序): 比较”的次数: “移多动”的次数 ∑ 2(n-1) 最坏的情况(关键字在记录序列中逆序有序): “比较”的次数: “移动”的次数 n(n ∑(+2) n-1)n+4) 总的平均比较和移动次数约为 ∑(2+2+2)=∑(+2)= (n-1)n+4)=O(n
对于直接插入排序： 最好的情况（关键字在记录序列中顺序有序）： “比较”的次数： 最坏的情况（关键字在记录序列中逆序有序）： “比较”的次数： 1 1 1 1 = − − = n n i 2(n-1) “移动”的次数： “移动”的次数： 2 ( 1) 1 1 − = − = n n i n i 2 ( 1)( 4) ( 2) 1 1 − + + = − = n n i n i 总的平均比较和移动次数约为 ( ) 2 ( 1)( 4) 2) ( 2) 2 2 ( 2 1 1 1 1 O n n n i i i n i n i = − + + + = + = − = − =
9.2.2折半插入排序 查找采用折半查找方法,称为二分插入排序或折半插入排序 public void BinInsertSorto/对R0.,n-1按递增有序进行折半插入排序 int i,j, low, high, mid; RecType tmp; for(i=l; i<length;i++) tmp=Rl /将R保存到mp中 low=0; high=i-1; while((low<=high)/在R[ow.high中折半查找有序插入的位置 i mid=(low+high)/2 取中间位置 if(tmp key<tImid. key) high=mid-1 /插入点在左半区 else low=mid+1 /插入点在右半区 for gj=i-1;j>=high+1; j--) /元素后移 RIj+lr; Rhigh+1=tmp; /插入原来的Ri
9.2.2 折半插入排序 查找采用折半查找方法，称为二分插入排序或折半插入排序。 public void BinInsertSort() //对R[0..n-1]按递增有序进行折半插入排序 { int i,j,low,high,mid;RecType tmp; for (i=1;i<length;i++) { tmp=R[i]; //将R[i]保存到tmp中 low=0;high=i-1; while (low<=high) //在R[low..high]中折半查找有序插入的位置 { mid=(low+high)/2; //取中间位置 if (tmp.key<R[mid].key) high=mid-1; //插入点在左半区 else low=mid+1; //插入点在右半区 } for (j=i-1;j>=high+1;j--) //元素后移 R[j+1]=R[j]; R[high+1]=tmp; //插入原来的R[i] } }
折半插入排序的元素移动次数与直接插入排序相同,不 同的仅是变分散移动为集合移动。在R|0.i1中查找插入R[引 的位置,折半查找的平均关键字比较次数为log2(计+1)-1,平均 移动元素的次数为i2+2,所以平均时间复杂度为 (log2(+1)-1++2)=O(n2) 就平均性能而言,折半查找优于顺序查找,所以折 半插入排序也优于直接插入排序。折半插入排序的空间 复杂度为O(1)
折半插入排序的元素移动次数与直接插入排序相同，不 同的仅是变分散移动为集合移动。在R[0..i-1]中查找插入R[i] 的位置，折半查找的平均关键字比较次数为log2 (i+1)-1，平均 移动元素的次数为i/2+2，所以平均时间复杂度为： 2) ( ) 2 (log ( 1) 1 2 1 1 2 O n i i n i + − + + = − = 就平均性能而言，折半查找优于顺序查找，所以折 半插入排序也优于直接插入排序。折半插入排序的空间 复杂度为O(1)
9.2.3希尔排序 希尔排序也是一种插入排序方法实际上是一种分组插入方法。 基本思想 先取定一个小于m的整数作为第一个增量,把表的全部记 录分成4个组,所有距离为d1的倍数的记录放在同一个组中, 在各组内进行直接插入排序 然后取第二个增量2(<d1),重复上述的分组和排序, 直至所取的增量l=1(4d41…<d2<d),即所有记录放在同 组中进行直接插入排序为止
9.2.3 希尔排序 希尔排序也是一种插入排序方法,实际上是一种分组插入方法。 基本思想： 先取定一个小于n的整数d1作为第一个增量，把表的全部记 录分成d1个组，所有距离为d1的倍数的记录放在同一个组中， 在各组内进行直接插入排序； 然后取第二个增量d2（＜d1），重复上述的分组和排序， 直至所取的增量dt =1（dt<dt-1<…<d2<d1），即所有记录放在同 一组中进行直接插入排序为止