9.1.1 插入排序（1）在线视频

同学们大家好

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

这张我们讨论内部排序

先介绍排序中的一些基本概念

排序是将一个数据元素或者说记录的任意系列

重新排列成一个按关键字有序的序列

这样一个过程，我们称为排序

假设含有n个记录的序列是R1，R2，到Rn

记录序列中

每个记录对应的关键字也形成一个序列K1,K2,到Kn

如果关键字序列中有ki等于kj，并且排序之前

Ri在序列中的位置领先于Rj，如果在排序后的有序序列中

Ri仍领先于Rj，则称所用的排序方法是稳定的

反之，若排序过程中，可能使排序后的序列中Rj领先于Ri

则称所用的排序方法是不稳定的

也就是说，不稳定的排序方法可能导致

关键字相等记录的相对位置发生改变

那么，同学们在选择排序方法时

应该结合问题背景的需要选择适当的排序方法

一般来说效率低的排序方法是稳定的

效率高的排序方法是不稳定的

为了后面讨论各种排序方法方便

先说明一下排序算法中涉及的数据存储结构

先定义存储记录的数组大小MAXSIZE为20

本章中约定给关键字的类型为整型

定义记录的类型为结构体，类型名为RedType

每个记录中有一个关键字成员key

排序记录序列的存储结构定义为结构体Sqlist

包含两个成员，一个是数组r，r的大小是maxsize+1

类型是RedType，数组r用来存储排序的记录序列

从r的1号单元开始存，0号单元不存记录

有的算法中0号单元闲置，有的算法中做监视哨

另外有一个整型的成员length，给出排序的有多少个记录

我们介绍的第一种排序算法是插入排序

首先介绍最简单的一种，直接插入排序

直接插入排序的排序的思路是

将一个记录插入到已排好序的有序表中

从而得到一个新的记录，数增1的有序表

结合一个例子来讨论直接插入排序算法

假设要进行的是自小到大的排序

待排序的序列如图1所示，序列中的有8个记录

图1中给出了8个记录的关键字，我们注意到

1号和8号单元中，两个记录的关键字都是49

为了区分这两个不同，但是关键字相等的记录

我们把8号单元的关键字49加下划线

这个49称为49杠

待排序序列中，49的位置在49杠之前

排序以后，通过观察二者的相对位置是否会变化

来说明所采用的排序方法是稳定的，还是不稳定的

采用直接插入排序方法

首先明确所谓已排好序的有序表

我们确定1号单元的记录49自己构成一个长度为1的有序表

表中只有一个记录，谈不上无序，随后通过循环

把记录序列中从i=2到i=n的记录渐插入到有序表中

有序表从前向后逐渐扩大

当第i个记录插入时，有序表是数组中1到i-1这段，长度为i-1

考虑把第i个记录插入有序表，自小到大的排序的话

有序表最后一个记录i-1的关键字是有序表中最大的关键字

把第i个记录的关键字和有序表最后一个记录的关键字进行比较

如果小于，说明需要把第i个记录插入到有序表中间

此时需要做2步，第1步，把第i个记录暂存到数组的0号单元

第2步，从有序表最后一个记录i-1开始

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

j赋值i-1，表示有序表最后一个元素的位置

利用j自后向前寻找插入位置。把0号单元的关键字

和j号单元的关键字比较

如果小于，则j号单元的记录移动到j+1号单元，j—

考察有序表前一个记录

如果0号单元的关键字大于等于j号单元的关键字

那么，j+1号单元就是第i个记录的插入位置

以i=2为例，第2个记录的关键字是38

和初始有序表最后一个记录的关键字49比较

38比49小，把关键字为38的记录暂存在0号单元

如图2所示，j=i-1=1，让j表示有序表最后一个记录的位置

比较38和j号单元的49，小于49

j号单元的记录49移动到j+1号单元

49移动到2号单元，j减1等于0

考察0号单元，这里0单元实际起到了监视哨的作用

因为自己不会小于自己

那么j+1的1号单元就是38的插入位置

结果如图3所示，我们获得了一个新的

记录数增1的有序表，就是数组中1-2这段

有序表中包含2个元素

考虑i=3的插入，65大于等于49

如果i的关键字大于等于有序表最后一个记录的关键字

不做任何操作，有序长度自动增1即可

i=3，i=4两个记录的情况相同

有序表自动延伸后如图4所示

此时有序表长度为4。i=5插入时

76小于97，那么需要插入到有序表中间

j=3时，76不小于65

那么76的插入位置是j+1等于4，插入后如图6所示

后续记录的插入情况类似，我们就不完整的讨论了

请同学们思考一个问题

直接插入排序是稳定的吗？

下面看一下，直接插入排序函数InsertSort的实现

函数返回值是无类型

涉及的参数只有排序序列的存储结构体L

函数for循环是从第2个元素开始

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

循环中，首先比较第i个记录的关键字

和有序表最后一个记录i-1的关键字

如果大于等于，有序表直接顺延，++i

插入下一个记录；如果小于

把L.r[i]赋值给L.r[0]暂存

随后的for循环，i-1赋值j

j表示有序表最后一个记录的位置

循环中把0号单元的关键字和j的关键字比较

如果小于，把j中的记录移动到j+1，j—考察有序表前一个

循环结束后，把0号单元的记录赋值j+1号单元

完成第i个记录的插入

随后继续完成外层循环，插入下一个记录

我们考察一下直接插入排序算法的效率

从排序的过程来看，算法的基本操作

主要是比较和移动，那么对直接插入排序来说

最好情况是初始序列是正序

这种情况下，直接插入排序算法中

只需要n-1次比较，不需要移动

最坏情况是逆序，这种情况

需要比较的次数是(n+2)(n-1)/2

移动的次数是(n+4)(n-1)/2

平均的比较次数和移动次数是4分之n方

从分析的结果看

算法时间复杂度是O(n2)

同学们，这节课就讲到这里，下次课再见