例如,n=6,数组R的六个排序码分别为:17,3,25, 14,20,9。它的直接插入排序的执行过程如图9-1所 小 R[O]R[R[2]R[3]R[4]R[S] 初始状态 (17) 第一次插入(3 17) 第二次插入(3 25) 20 第三次插入(3 17 第四次插入(3 14 1720 25) 第五次插入(39 17 20 25) 图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次,移动i+2次(逆序) (i=1,2,…,n-1)。若分别用Cmn,Cmax和Cmg表示 元素的总比较次数的最小值、最大值和平均值,用Mnn A、和M、表示元素的总移动次数的最小值、最大值和 平均值,则上述直接插入算法对应的这些量为: C=n-1 M=2(n-1) mIn C.=1+2++n-1=(n2-n)/2 3+4+..+n+1 max max (n2+3n-4)/2 C.=(n2+n-2)/4 (n2+7n-8)/4 因此,直接插入排序的时间复杂度为O(n2) 直接插入算法的元素移动是顺序的,该方法是稳定的
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）。 直接插入算法的元素移动是顺序的，该方法是稳定的
922二分插入排序 二分插入排序的基本思想 二分插入排序( Binary Insert Sort)的基本思想是: y在有序表中采用二分查找的方法查找待排元素的插 入位置 其处理过程:先将第一个元素作为有序序列,进行n 1次插入,用二分查找的方法查找待排元素的插入位 置,将待排元素插入。 3.二分插入排序的效率分析 分插入算法与直接插入算法相比,需要辅助空间与直接 插入排序基本一致;时间上,前者的比较次数比直接插入 査找的最坏情况好,最好的情况坏,两种方法的元素的移 动次数相同,因此二分插入排序的时间复杂度仍为O (n2) 二分插入算法与直接插入算法的元素移动一样是顺序的, 因此该方法也是稳定的
9.2.2二分插入排序 1．二分插入排序的基本思想 二分插入排序（Binary Insert Sort）的基本思想是： 在有序表中采用二分查找的方法查找待排元素的插 入位置。 其处理过程：先将第一个元素作为有序序列，进行n- 1次插入，用二分查找的方法查找待排元素的插入位 置，将待排元素插入。 3．二分插入排序的效率分析 二分插入算法与直接插入算法相比，需要辅助空间与直接 插入排序基本一致；时间上，前者的比较次数比直接插入 查找的最坏情况好，最好的情况坏，两种方法的元素的移 动次数相同，因此二分插入排序的时间复杂度仍为O （n 2）。 二分插入算法与直接插入算法的元素移动一样是顺序的， 因此该方法也是稳定的
2.二分插入排序的算法实现 其算法如下: void BinaryInsertSort(ElemType R[,int n) for(inti=1;i<n;i+)∥共进行n-1次插入 i int left=0, right=1-1; ElemType temp=R[] while(left<=right) int middle=( left+right))2;∥取中点 ftmp<R[ middle]) right= middle-l;∥取左区间 else left=middle+;i /取右区间 for(int j=1-1; j>=left; j-) R[j+1]=R[j]; ∥元素后移空出插入位 R[left]=temp; 3)
2．二分插入排序的算法实现 其算法如下： void BinaryInsertSort(ElemType R[],int n) { for(int i=1; i<n; i++) //共进行n-1次插入 { int left=0,right=i-1;ElemType temp=R[i]; while(left<=right) { int middle=(left+right)/2; //取中点 if(temp<R[middle]) right=middle-1; //取左区间 else left=middle+1; } //取右区间 for(int j=i-1;j>=left;j--) R[j+1]=R[j]; //元素后移空出插入位 R[left]=temp; }}
923希尔排序 1.希尔排序的基本思想 希尔排序( Shell sort)又称为“缩小增量排序”。是 y1959年由 D.L. Shell提出来的。该方法的基本思想是:先 将整个待排元素序列分割成若干个子序列(由相隔某个 “增量”的元素组成的)分别进行直接插入排序,待整 个序列中的元素基本有序(增量足够小)时,再对全体 元素进行一次直接插入排序。因为直接插入排序在元素 基本有序的情况下(接近最好情况),效率是很高的, 因此希尔排序在时间效率上比前两种方法有较大提高。 3.希尔排序的效率分析 虽然我们给出的算法是三层循环,最外层循环为logn数 量级,中间的for循环是n数量级的,内循环远远低于n数 量级,因为当分组较多时,组内元素较少;此循环次数 少;当分组较少时,组内元素增多,但已接近有序,循 环次数并不增加。因此,希尔排序的时间复杂性在O (nlog2n)和O(n2)之间,大致为O(n13)
9.2.3希尔排序 1．希尔排序的基本思想 希尔排序（Shell Sort）又称为“缩小增量排序” 。是 1959年由D.L.Shell提出来的。该方法的基本思想是：先 将整个待排元素序列分割成若干个子序列（由相隔某个 “增量”的元素组成的）分别进行直接插入排序，待整 个序列中的元素基本有序（增量足够小）时，再对全体 元素进行一次直接插入排序。因为直接插入排序在元素 基本有序的情况下（接近最好情况），效率是很高的， 因此希尔排序在时间效率上比前两种方法有较大提高。 3．希尔排序的效率分析 虽然我们给出的算法是三层循环，最外层循环为log2 n数 量级，中间的for循环是n数量级的，内循环远远低于n数 量级，因为当分组较多时，组内元素较少；此循环次数 少；当分组较少时，组内元素增多，但已接近有序，循 环次数并不增加。因此，希尔排序的时间复杂性在O （nlog2 n）和O（n 2 ）之间，大致为O（n 1. 3）