9.1.2 插入排序（2）在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这节我们继续讨论插入排序

上一节，我们讨论了直接插入排序算法

这一节我们介绍两个改进的插入排序算法

第1是折半插入排序

折半插入排序的基本排序思路是

查找插入位置的过程，利用折半查找来实现

前面讨论过直接插入排序算法

基本每次循环把第i个记录插入到有序表1到i-1中

当第i个记录的关键字小于有序表最后一个记录的关键字

需要从有序表最后一个记录i-1开始

自后向前进行比较，寻找第i个记录在有序表中的插入位置

直接插入排序算法中，我们是边比较移动，边寻找位置

考虑到1到i-1是有序表

我们可以通过在有序表中进行折半查找来确定

第i个记录的插入位置，确定插入位置后

再统一后移需要移动的记录，随后插入第i个记录

我们看图1中的示例

假设i=6，记录关键字是13

要把记录i插入到1到5的有序表中

首先通过折半查找确定关键字13的插入位置

初始时low=1，high=5，计算mid=3

和3号单元的65比较，13小于65

high=mid-1=2，继续计算mid=1，和1号单元的38比较

13小于38，high=mid-1=0

此时，high小于low，查找范围消失

折半查找结束，关键字为13记录插入位置是high+1

示例中是1号单元。确定了插入位置是1号单元以后

把有序表中的1~5号单元中的记录后移到2~6号单元

完成后赋值关键字为13记录到1号单元，完成有序表的插入

下面我们看一下折半插入排序的实现

外层for循环和直接插入排序中相同

目的是把i=2到L.length的记录插入到有序表1到i-1中

low=1，high=i-1

设置折半查找的范围

随后利用一个当循环

折半寻找插入的位置

折半查找的过程我们介绍过

注意黄色这段代码

因为这里折半查找的目标是确定插入的位置

所以没有相等，查找成功的情况

如果小于就到前半区间去查找

大于等于都是到后半区间继续查找

当循环结束以后，high+1这个位置

就是记录i的插入位置

随后利用一个for循环，从最后一个记录开始

把有序表中high+1到j-1这段依次后移

最后把存放在0号单元的记录赋值到high+1单元

完成插入

折半插入排序对直接插入排序的主要改进是利用了折半查找

在有序表中确定记录i的插入位置

相对于直接插入排序而言，比较的次数减少了

但移动的次数和直接插入排序是完全一样的

另一个对于直接插入排序的改进是二路插入排序

二路插入排序的思路是：另设一个和L.r同类型的数组d

首先将L.r[1]赋值d[0]，并将d[0]看成是

排好序的序列中处于中间位置的记录

然后从L.r中第2个记录起

依次插入到

d[0]之前或之后的有序序列中

比49小的插入到49之前的有序序列

大于等于49的插入49之后的有序序列

如图所示

图1中，待排序序列存放在数组L.r中

按算法思路

把序列第1个关键字为49记录放到数组d的0号单元

为后续插入方便，设置两个整型变量first.和final

其中first指示49之前的有序序列中

最小的一个元素的位置，final指示49之后

有序序列中最大一个元素的位置

初始时，序列只有一个元素

first和final都指示49的位置

从i=2到L.length把序列中的记录逐个插入数组d

首先插入i=2，关键字等于38的记录

和0号单元的关键字49比，比49小

应该插入49之前的序列

把38和first指示的关键字比较，现在是49

比它小，插入first之前

这里d被看作一个循环向量

first之前是7号单元，38移动到7号单元

现在38是序列中最小一个

first重置指向38，结果如图2所示

下一个插入的是65,65大于49

应该插入49之后的序列

把65和final指示的关键字比较

现在是49，比它大，插入final之后的1号单元

现在65是序列中最大一个，final重置指向65

第3个记录97的情况同65

插入后的情况如图2所示

目前的有序序列从first到final包含4个记录

后续记录的插入以此类似，按照直接插入排序的方法

插入49之前或之后的序列中就可以了

完成所有记录插入后的情况如图3所示

随后，需要把d中的记录移动回数组L.r中

移动从first指示的位置开始，向后逐个移动

移动最小的2个13和27后

如图4所示，一直向后移动到final，完成2路插入排序

所谓2路，指的就是比L.r[1]小的1路

L.r[1]大的1路，如果L.r[1]比较恰当的话

也就是说，如果它是序列中处于中位的关键字

那么插入一个记录时候

只需要进行一半数量的移动

移动的次数可以减少到n2/8

代价是增加一个数组作为存储空间

当然如果L.r[1]不恰当

比如说是序列中最小或最大的关键字

那么2路插入排序的效率不会有任何改善

好，同学们，这节课

就讨论到这，下次课再见