第9章 内部排序
直接插入排序算法简便，比较适用于待排序记录数目较少
且基本有序的情况。当待排记录数目较大时，直接插入排序的
性能就不好， 为此我们可以对直接插入排序做进一步的改进。 在直接插入排序法的基础上，从减少“比较关键字”和“移动 记录”两种操作的次数着手来进行改进。
第9章 内部排序
9.2.2 折半插入排序
列中，将所有间隔为d2的记录分成一组，进行组内直接插入排序，
第9章 内部排序
49 38 65 97 76 13 27 49 55 04
d1 5
13 27 49 55 04 49 38 65 97 76
d2 3
d3 2
13 04 49 38 27 49 55 65 97 76 13 04 27 38 49 49 55 65 97 76 04 13 27 38 49 49 55 65 76 97
序，要求找出当前下标序列1，2，…， n的一种排列p1，p2， …，
pn，使得相应关键字满足如下的非递减（或非递增）关系，即：
Kp1≤Kp2≤…≤Kpn，这样就得到一个按关键字有序的记录序列{Rp1， Rp2，…，Rpn}。
第9章 内部排序
2. 内部排序与外部排序
根据排序时数据所占用存储器的不同，可将排序分为两
第9章 内部排序
49 38 65 97 76 13 27 49
初 始 关 键 字
第9章 内部排序
0
1
2
3
4
5
6
7
8
i7
Max 49 38 65 97 76 13 27 49
6
0
3
1
1 5 0 4 7 2
2
3
4
5
6
7
8
i 8
Max 49 38 65 97 76 13 27 49
6
8
1 5 0 4 7 2 3
第9章 内部排序
9.2.5 希尔排序(shell)
又称“缩小增量排序”。希尔排序的基本思想：先将待排序 记录序列分割成为若干个子序列，分别进行直接插入排序。待
第9章 内部排序
9.2.3 2-路插入排序 P267
引入：改进的折半插入排序，为减少移动记录的次数， 为此需n个记录的辅助空间。 做法：另设一个和L.r同类型的数组d，首先将L.r[1]赋 给d[1]，并将d[1]看成是在排好序的序列中处于中间位 置的记录，然后从L.r中第2个记录起依次插入到d[1]之
final
第9章 内部排序
9.2.4 表插入排序
采用链表存储结构进行插入排序。表插入排序的基本思 想是：先在待插入记录之前的有序子链表中查找应插入位置， 然后将待插入记录插入链表。由于链表的插入操作只修改指 针域，不移动记录，所以表插入排序可提高排序效率。在算 法的具体实现上，我们可以采用静态链表作为存储结构。
整个序列中的记录基本有序时，再对全部记录进行一次直接插入
排序。 具体实现时，首先选定两个记录间的距离d1，在整个待排序 记录序列中将所有间隔为d1的记录分成一组，进行组内直接插入 排序，然后再取两个记录间的距离d2<d1，在整个待排序记录序 直至选定两个记录间的距离dt=1为止，此时只有一个子序列，即 整个待排序记录序列。
已排好序的单元素子集合，然后将第2个记录插入到单元素子
集合中。i从2循环到n，即可实现完整的直接插入排序。
第9章 内部排序
例9.1 设有一组关键字序列｛55，22，44，11，33｝，这
里n=5，即有5个记录。如图9.1所示。请将其按由小到大的顺序 排序。
第一趟 第二趟 第三趟 第四趟 结 果 [55] [22 [22 [11 [11 22 55] 44 22 22 44 44 55] 44 33 11 11 11 55] 44 33 33 33 33 55]
前或之后的有序序列中。
第9章 内部排序
1
2
i 2 i 1
i
i 1
L.r
1
2
i 2 i 1
i
i 1
辅助空间d：
将d看成是一个循环向量，并设两个指针first和final指示 有序序列中第一个记录和最后 65 97 76 13 27 49
void BInsertSort(SqList &L) { // 对顺序表L作折半插入排序。算法10.2 for(i=2;i<=L.length;++i) { L.r[0]=L.r[i]; // 将L.r[i]暂存到L.r[0] low=1; high=i-1; while(low<=high) { // 在r[low..high]中折半查找有序插入的位置 m=(low+high)/2; // 折半 if LT(L.r[0].key,L.r[m].key) high=m-1; //插入点在低半区 else low=m+1; // 插入点在高半区 } for(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; // 记录后移 L.r[high+1]=L.r[0]; // 插入 } }
第9章 内部排序
0
1
2
3
4
5
6
7
8
初始状态：
Max 49 38 65 97 76 13 27 49
key 域 next 域
1
0
0
1 2
3
4
5
6
7
8
i2
Max 49 38 65 97 76 13 27 49
2
0
0
1
1
2
3
4
5
6
7
8
i3
Max 49 38 65 97 76 13 27 49
2
3
1
0
记录序列，有三种常见的存储表示方法: · 向量结构：将待排序的记录存放在一组地址连续的存储单 元中。由于在这种存储方式中，记录之间的次序关系由其存储位 置来决定，所以排序过程中一定要移动记录才行。
第9章 内部排序
· 链表结构：采用链表结构时，记录之间逻辑上的相邻
性是靠指针来维持的，这样在排序时，就不用移动记录元素，
第9章 内部排序
为了讨论方便，假设待排记录的关键字均为整数，均从 数组中下标为1的位置开始存储，下标为0的位置存储监视哨， 或空闲不用。 typedef int KeyType; typedef struct { KeyType key; OtherType other-data; } RecordType;
证明一种排序方法是稳定的，要从算法本身的步骤中加以
证明。 证明排序方法是不稳定的，只需给出一个反例说明。
第9章 内部排序
在排序过程中，一般进行两种基本操作： （1） 比较两个关键字的大小；
（2） 将记录从一个位置移动到另一个位置。
其中操作（1）对于大多数排序方法来说是必要的，而操作
（2）则可以通过采用适当的存储方式予以避免。对于待排序的
类: 一类是整个排序过程完全在内存中进行，称为内部排序； 另一类是由于待排序记录数据量太大，内存无法容纳全部数 据， 排序需要借助外部存储设备才能完成，称为外部排序。
第9章 内部排序
假设Ki=Kj(1≤i≤n，1≤j≤n，i≠j)， 若在排序前的序列中Ri
领先于Rj(即i<j)，经过排序后得到的序列中Ri仍领先于Rj， 则 称所用的排序方法是稳定的；反之，当相同关键字的领先关系 在排序过程中发生变化，则称所用的排序方法是不稳定的。 无论是稳定的还是不稳定的排序方法，均能排好序。在应 用排序的某些场合，如选举和比赛等，对排序的稳定性是有特 殊要求的。
图9.1 直接插入排序示例
第9章 内部排序
假设待排序记录存放在r[1..n]之中，为了提高效率，我们 附设一个监视哨r[0]，使得r[0]始终存放待插入的记录。监视 哨的作用有两个：一是备份待插入的记录，以便前面关键字 较大的记录后移；二是防止越界，具体算法描述如下：
第9章 内部排序
void InsertSort(SqList *L) { // 对顺序表L作直接插入排序。算法10.1 for(i=2;i<=L.length;++i) if (LT(L.r[i].key,L.r[i-1].key) // "<",需将L.r[i]插入有序子表 {
第9章 内部排序
0
1 2
3
4
5
6
7
8
i4
Max 49 38 65 97 76 13 27 49
2
0
3
1
1 4 0
2
3
4
5
6
7
8
i5
Max 49 38 65 97 76 13 27 49
2
0
3
1
1 5 0 4
2
3
4
5
6
7
8
i6
Max 49 38 65 97 76 13 27 49
6
3
1 5 0 4 2
i 1: i 2: i 3: i 4: i 8:
first first
（49）
first
final
(38) (49)
final final final
(38) (49) (65)
first
first
(38) (49) (65) (97)
(13 27 38 49 49 65 76 97 )
第9章 内部排序
9.2.1 直接插入排序
直接插入排序是一种最基本的插入排序方法。其基本操作
是将第i个记录插入到前面i-1个已排好序的记录中，具体过程 为： 将第i个记录的关键字Ki顺次与其前面记录的关键字Ki-1， Ki-2，…, K1进行比较，将所有关键字大于Ki的记录依次向后移 动一个位置，直到遇见一个关键字小于或者等于Ki的记录Kj， 此时Kj 后面必为空位置，将第i个记录插入空位置即可。完整 的直接插入排序是从i=2开始的，也就是说，将第1个记录视为