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