i=4:(496597) (38) 个fna ↑frst 结i=5:(49657697 个fnal 个frst i=6:(49657697) (1338) 个f 部i=7: 49657697) (132738) 序 个fnal 个frst i-8:(4949657697132738) 个 个frst 与折半插入排序相比,2路插入排序可以减 据 构 少记录移动的次数,但不能避免记录的移动。 此外需要N个额外的存储空间。并且如果Lr 是待排序记录中关键字最小(或最大)的记录 排 时,2路排序就没有优越性可言了。 189 数 据 结 构 之 内 部 排 序 17 i=4: (49 65 97) (38) ↑final ↑first i=5: (49 65 76 97) (38) ↑final ↑first i=6: (49 65 76 97) (13 38) ↑final ↑first i=7: (49 65 76 97) (13 27 38) ↑final ↑first i=8: (49 49 65 76 97 13 27 38) ↑final ↑first 数 据 结 构 之 内 部 排 序 18 与折半插入排序相比，2路插入排序可以减 少记录移动的次数，但不能避免记录的移动。 此外需要N个额外的存储空间。并且如果L.r[1] 是待排序记录中关键字最小（或最大）的记录 时，2路排序就没有优越性可言了