设待排序的7记录的排序码为312,126,272 226,28,165,123},在前6个记录已经排序的情況 下,使用二分法插入排序算法插入第7个记录的排序码 123的执行过程示意如图10.3所示(见书本)。 二分法插入排序算法,在查找第记录的插入位 置时,每执行一次whie循环体,查找范围缩小一半 和直接插入排序的比较次数对比,二分法插入的比较 次数少于直接插入排序的最多比较次数,而一般要多 于直接插入排序的最少比较次数。总体上讲,当n较 大时,二分法插入排序的比较次数远少于直接插入排 序的平均比较次数,但二者所要进行的移动次数相等 故二分法插入排序的时间复杂度也是○(n2),所需的附 加存储空间为一个记录空间
设待排序的7记录的排序码为{312，126，272， 226，28，165，123}，在前6个记录已经排序的情况 下，使用二分法插入排序算法插入第7个记录的排序码 123的执行过程示意如图10.3所示（见书本）。 二分法插入排序算法，在查找第i个记录的插入位 置时，每执行一次while循环体，查找范围缩小一半， 和直接插入排序的比较次数对比，二分法插入的比较 次数少于直接插入排序的最多比较次数，而一般要多 于直接插入排序的最少比较次数。总体上讲，当n较 大时，二分法插入排序的比较次数远少于直接插入排 序的平均比较次数，但二者所要进行的移动次数相等， 故二分法插入排序的时间复杂度也是O(n2 )，所需的附 加存储空间为一个记录空间
1023表插入排序 二分法插入排序比较次数通常比直接插入排序的 比较次数少,但移动次数相等。表插入排序将在不进 行记录移动的情况下,利用存储结构有关信息的改变 来达到排序的目的。 给每个记录附设一个所谓的指针域lnk,它的类型 为整型,表插入排序的思路:在插入第个记录R时, R, R R已经通过各自的指针域ink按排序码 不减的次序连接成一个(静态链)表,将记录R的排 序码key与表中已经排好序的排序码从表头向右、或 称向后依次比较,找到R应插入的位置,将其插入在 表中,使表中各记录的排序码仍然有序
10.2.3 表插入排序 二分法插入排序比较次数通常比直接插入排序的 比较次数少，但移动次数相等。表插入排序将在不进 行记录移动的情况下，利用存储结构有关信息的改变 来达到排序的目的。 给每个记录附设一个所谓的指针域link，它的类型 为整型，表插入排序的思路：在插入第i个记录Ri时， R1，R2，…，Ri-1已经通过各自的指针域link按排序码 不减的次序连接成一个（静态链）表，将记录Ri的排 序码keyi与表中已经排好序的排序码从表头向右、或 称向后依次比较，找到Ri应插入的位置，将其插入在 表中，使表中各记录的排序码仍然有序