//在r[0]处设置监视哨void insertsort(Sqlist &L)( for ( i-2; i<=L.length, i++)if (L.r[i].key<L.r[i-1].key)L.r[O]=L.r[i];//复制为哨兵L.r[i]-L.r[i-1];j=i-2;while (L.r[O].key<L.r[i].key)(L.r[i+1]=L.r[i];j--;} //记录后移/插入到适当位置L.r[j+1]-L.r[O];人
//在r[0]处设置监视哨 void insertsort(Sqlist &L) { for ( i=2; i<=L.length; i++) if (L.r[i].key<L.r[i-1].key){ L.r[0]=L.r[i]; //复制为哨兵 L.r[i]=L.r[i-1]; j=i-2; while (L.r[0].key<L.r[j].key ) {L.r[j+1]=L.r[j]; j-;} //记录后移 L.r[j+1]=L.r[0]; //插入到适当位置 } }
例如，n=6，数组R的六个排序码分别为：17，3，2514，20，9。它的直接插入排序的执行过程如图9-1所示。R[4]R[0]R[1]]R[2]R[3]R[5]9251420初始状态3(17)25第一次插入(317)142099(31720第二次插入25)14V14(3179第三次插入25)20(3141720第四次插入25)9141720第五次插入(3925)图9-1直接插入排序示例
例如，n=6，数组R的六个排序码分别为：17，3，25， 14，20，9。它的直接插入排序的执行过程如图9-1所 示。 R[0] R[1] R[2] R[3] R[4] R[5] 初始状态 (17 ) 3 25 14 20 9 第一次插入 (3 17 ) 25 14 20 9 第二次插入 (3 17 25 ) 14 20 9 第三次插入 (3 14 17 25 ) 20 9 第四次插入 (3 14 17 20 25 ) 9 第五次插入 (3 9 14 17 20 25) 图 9-1 直接插入排序示例
3.直接插入排序的效率分析从上面的叙述可以看出，直接插入排序算法十分简单。那么它的效率如何昵？首先从空间来看，它只需要一个元素的辅助空间，用于元素的位置交换。从时间分析，首先外层循环要进行n-1次插入，每次插入最少比较一次（正序），移动两次：最多比较i次，移动十2次（逆序）（i=l，2，..，n-1）。若分别用Cmin，Cmax和Caye表示元素的总比较次数的最小值、最大值和平均值，用Mmin，M和M表示元素的总移动次数的最小值、最大值和平均值，则上述直接插入算法对应的这些量为：Cmin=n-1Mmin=2 (n-1)M max=3+4+... +n+1= (n?+3n-4)Cmax=1+2+...+n-1= (n2-n) /212Cave=（n2+n-2) /4Mmax=（n2+7n-8）/4因此，直接插入排序的时间复杂度为O（n?）。直接插入算法的元素移动是顺序的，该方法是稳定的
3．直接插入排序的效率分析 从上面的叙述可以看出，直接插入排序算法十分简单。那么它的效 率如何呢？首先从空间来看，它只需要一个元素的辅助空间，用于 元素的位置交换。从时间分析，首先外层循环要进行n-1次插入， 每次插入最少比较一次（正序），移动两次；最多比较i次，移动i ＋2次（逆序）（i=1，2，.，n-1）。若分别用Cmin ，Cmax 和Cave表 示元素的总比较次数的最小值、最大值和平均值，用Mmin ，Mmax 和Mave表示元素的总移动次数的最小值、最大值和平均值，则上述 直接插入算法对应的这些量为： Cmin=n-1 M min=2（n-1） Cmax=1+2+.+n-1=（n 2 -n）/2 M max=3+4+.+n+1=（n 2+3n-4） /2 Cave=（n 2+n-2）/4 M max=（n 2+7n-8）/4 因此，直接插入排序的时间复杂度为O（n 2）。 直接插入算法的元素移动是顺序的，该方法是稳定的
9.2.2二分插入排序（折半插入排序）1.二分插入排序的基本思想二分插入排序（BinaryInsertSort）的基本思想是：在有序表中采用二分查找的方法查找待排元素的插入位置。其处理过程：先将第一个元素作为有序序列，进行n1次插入，用二分查找的方法查找待排元素的插入位置，将待排元素插入。3.二分插入排序的效率分析二分插入算法与直接插入算法相比，需要辅助空间与直接插入排序基本一致；时间上，前者的比较次数比直接插入查找的最坏情况好，最好的情况坏，两种方法的元素的移动次数相同，因此二分插入排序的时间复杂度仍为0(n?)。二分插入算法与直接插入算法的元素移动一样是顺序的，因此该方法也是稳定的
9.2.2二分插入排序（折半插入排序） 1．二分插入排序的基本思想 二分插入排序（Binary Insert Sort）的基本思想是： 在有序表中采用二分查找的方法查找待排元素的插 入位置。 其处理过程：先将第一个元素作为有序序列，进行n- 1次插入，用二分查找的方法查找待排元素的插入位 置，将待排元素插入。 3．二分插入排序的效率分析 二分插入算法与直接插入算法相比，需要辅助空间与直接 插入排序基本一致；时间上，前者的比较次数比直接插入 查找的最坏情况好，最好的情况坏，两种方法的元素的移 动次数相同，因此二分插入排序的时间复杂度仍为O （n 2）。 二分插入算法与直接插入算法的元素移动一样是顺序的， 因此该方法也是稳定的
2．二分插入排序的算法实现voidBInsertSort(Sqlist&L)（for(i=2;i<=L.length;i++）（//共进行n-1次插入L.r[O]=L.r[i];low=1;high=i-1;while (low<-high)m=(low+high)/2;if(L.r[O].key<L.r[m].key) high=m-1;else low=m+1;)for(j=i-1;j>=high+1;j--) L.r[j+1]-L.r[i];L.r[high+1]-L.r[O];]7
2．二分插入排序的算法实现 void BInsertSort(Sqlist &L) { for( i=2; i<=L.length; i++) { //共进行n-1次插入 L.r[0]=L.r[i]; low=1;high=i-1; while (low<=high){ m=(low+high)/2; if(L.r[0].key<L.r[m].key) high=m-1; else low=m+1;} for(j=i-1;j>=high+1;j-) L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0];} }