设待排序的7记录的排序码为{312,126,272,226,28,165 123},直接插入排序算法的执行过程如图10.2所示 肖兵 排序码 312,126,272,226,28,165,123 初始( 312],126,272,226,28,165,123 i=2:(126)[126,312],272,226,28,165,123 3:(272)[126,272,312],226,28,165,123 4:(226)[126,226,272,312],28,165,123 5:(28)[28,126,226,272,312],165,123 6:(165)[28,126,165,226,272,312],123 7:(123)[28,123,126,165,226,272,312] 图102直接插入排序算法执行过程示意图
设待排序的7记录的排序码为{312，126，272，226，28，165， 123}，直接插入排序算法的执行过程如图10.2所示。 哨兵 排序码 [] 312，126，272，226，28，165，123 初始 （） [312]，126，272，226，28，165，123 i=2： （126） [126，312]，272，226，28，165，123 i=3： （272） [126，272，312]，226，28，165，123 i=4： （226） [126，226，272，312]，28，165，123 i=5： （28） [28，126，226，272，312]，165，123 i=6： （165） [28，126，165，226，272，312]，123 i=7： （123） [28，123，126，165，226，272，312] 图10.2 直接插入排序算法执行过程示意图
直接插入排序算法执行时间的分析 最好的情况 即初始排序码开始就是有序的情况下,因为当插 入第个排序码时,该算法内循环Whie只进行一次条件 判断而不执行循环体,外循环共执行n-1次,其循环体 内不含内循环每次循环要进行2次移动操作,所以在最 好凊况下,直接插入排序算法的比较次数为(n-1)次 移动次数为2*(n-1次
直接插入排序算法执行时间的分析： 最好的情况 ： 即初始排序码开始就是有序的情况下，因为当插 入第i个排序码时，该算法内循环while只进行一次条件 判断而不执行循环体，外循环共执行n-1次，其循环体 内不含内循环每次循环要进行2次移动操作，所以在最 好情况下，直接插入排序算法的比较次数为(n-1)次， 移动次数为2*(n-1)次
最坏情况 即初始排序码开始是逆序的情况下,因为当插入 第个排序码时,该算法内循环 While要执行ⅸ条件判 断,循环体要执行i次,每次要移动1个记录,外循 环共执行η-1次,其循环体内不含内循环每次循环要 进行2次移动操作,所以在最坏情况下,比较次数为 (1+2+…+n)*(n-1),移动次数为 (1+2+2+2+…+n+2)*(n-1)。假设待排序文件中的记录 以各种排列出现的概率相同,因为当插入第个排序码 时,该算法内循环 While平均约要执行2次条件判断 循环体要执行(计)2次,外循环共执行n-1次,所以 平均比较次数约为(2+3++n)2*(-1),平均移动次 数为(n-1)*(2+1+3+1+…n+1)2,也即直接插入排序 算法的时间复杂度为O(n2)
最坏情况 ： 即初始排序码开始是逆序的情况下，因为当插入 第i个排序码时，该算法内循环while要执行i次条件判 断，循环体要执行i-l次，每次要移动1个记录，外循 环共执行n-1次，其循环体内不含内循环每次循环要 进行2次移动操作，所以在最坏情况下，比较次数为 (1+2+…+n)*(n-1)，移动次数为 (1+2+2+2+…+n+2)*(n-1)。假设待排序文件中的记录 以各种排列出现的概率相同，因为当插入第i个排序码 时，该算法内循环while平均约要执行i/2次条件判断， 循环体要执行（i-l）/2次，外循环共执行n-1次，所以 平均比较次数约为(2+3+…+n)/2*(n-1)，平均移动次 数为(n-1)*(2+1+3+1+…+n+1)/2，也即直接插入排序 算法的时间复杂度为O(n2 )
1022二分法插入排序 二分法插入排序的思想: 根据插入排序的基本思想,在找第记录的插入 位置时,前个记录已排序,将第价个记录的排序码 key和已排序的前-1个的中间位置记录的排序码进 比较,如果key小于中间位置记录排序码,则可以在 前半部继续使用二分法查找,否则在后半部继续使用 分法查找,直到查找范围为空,即可确定key的插 入位置
10.2.2 二分法插入排序 二分法插入排序的思想： 根据插入排序的基本思想，在找第i个记录的插入 位置时，前i-l个记录已排序，将第i个记录的排序码 key[i]和已排序的前i-1个的中间位置记录的排序码进行 比较，如果key[i]小于中间位置记录排序码，则可以在 前半部继续使用二分法查找，否则在后半部继续使用 二分法查找，直到查找范围为空，即可确定key[i]的插 入位置
void binarysort (table *tab) f int i,j, left, right, mid for(i=2;i<=tab-> length;++)/依次插入从第2个开始的所有元素 tab->r0]key=tab->key;/保存待插入的元素* left=1; right=i-1 /设置查找范围的左、右位置值 While(eft≤=righ /查找第个元素的插入位置* md=( eft +right)/2;/"取中点位置 if(tab->r[]. key stab->rmid]. key) right=mid-1 ise left=mid+1 /插入位置为|ef* for(j=i-1j>=lefj-)tab->[+1]key=tab->r]key;/后移空出插入位置 tab-> r[left] key=tab-> r[o]. key;/插入第个元素的副本 /算法10.2二分法插入排序算法*
void binarysort(table *tab) { int i,j,left,right,mid; for(i=2;i<=tab->length;i++) /*依次插入从第2个开始的所有元素*/ { tab->r[0].key=tab->r[i].key; /*保存待插入的元素*/ left=1;right=i-1; /*设置查找范围的左、右位置值*/ while(left<=right) /*查找第i个元素的插入位置*/ { mid=(left+right)/2; /*取中点位置*/ if(tab->r[i].key<tab->r[mid].key) right=mid-1; else left=mid+1; } /*插入位置为left*/ for(j=i-1;j>=left;j--) tab->r[j+1].key=tab->r[j].key; /*后移,空出插入位置*/ tab->r[left].key=tab->r[0].key; /*插入第i个元素的副本*/ } } /*算法10.2 二分法插入排序算法 */