1北京邮电大学自动化学院
第 9章 排序
? 9.1 概述 ? 1、排序
? 排序 是计算机程序设计中的一种重要操作，它的功能是将一个
数据元素（或记录）的任意序列，重新排列成一个按关键字有
序序列。
? 其相应的关键字序列为
? {K1,K2,……, K n}，
? 假设含 n个记录的序列为：
? {R1,R2,……, R n} (9.1）
? 需确定 1,2,……, n的一种排列 P1,P2,……, P n，使其相
应的关键字满足如下的非递减（或非递增）关系
KP1?KP2?…… ?KP n，即使（ 9.1）式的序列成为一个按关键字
有序的序列 {RP1,RP2,……, RPn}，这样一种操作称为 排序 。
2北京邮电大学自动化学院
? 2、稳定的、非稳定的
? 3、内部排序、外部排序
? 假设 Ki=Kj（ 1 ? i ? n,1 ? j ? n,i?j）且在排序前的序列中
Ri领先 Rj（即 i<j）。
? 内部排序,指的是待排序记录存放在计算机随机存储器中
进行的排序过程。
? 外部排序,指的是排序记录的数量很大，以致内存一次
不能容纳全部记录，在排序过程中尚需对外存进行访问
的排序过程。
? 反之，若可能使排序后的序列中 Rj领先于 Ri，则称所用的
排序方法是 不稳定的 。
? 若在排序后的序列中 Ri仍领先 Rj，则称所用的排序方法是 稳
定的 ；
3北京邮电大学自动化学院
? 4、排序方法
? 插入排序,直接插入排序、折半插入排序、希尔排序
? 交换排序,冒泡排序、快速排序
? 选择排序,简单选择排序、树形选择排序、堆排序
? 归并排序, 2-路归并排序
? 基数排序, 多关键字排序、链式基数排序
? 如果按内部排序过程中所需的工作量来区分，可分为：
? （ 1）简单排序,其时间复杂度为 T(n)=O(n2)
? （ 2） 先进的排序方法, 其时间复杂度为 T(n)=O(nlogn)
? （ 3） 基数排序, 其时间复杂度为 T(n)=O(d.n)
? 5,排序基本操作,
? （ 1）比较两个关键字大小；
? （ 2）将记录从一个位置移动到另一个位置。
4北京邮电大学自动化学院
? 插入排序的基本思想是,每一步将一个待排序的记录，按
其主关键字的大小插入到前面已经排序的文件中适当位置
上，直至全部插完为止。
9.1 插入排序
? 1、直接插入排序
? 直接插入排序是一种最简单的排序方法，它的基本操作
是将一个记录插入到已排好的有序表中，从而得到一个
新的、记录数增加 1的有序表。
? 例如：已知待排序的一组记录的初始排列如下所示,R
（ 49）,R（ 38）,R（ 65）,R（ 97）,R（ 76）,R
（ 13）,R（ 27）,R（ 19）。
5北京邮电大学自动化学院
1、直接插入排序
? 假设在排序过程中，前四个记录已按关键字递增的次序，重
新排列，构成一个含 4个记录的有序序列,
? 现要将第 5个（关键字为 76）的记录插入上述序列，可以得
到一个新的含 5个记录的有序序列,则首先要找到插入的位
置，然后进行插入。
? 假设从 R（ 97）起向左进行顺序查找，由于 65 ?76 ? 97，则
R（ 76）应插入在 R（ 65）和 R（ 97）之间，从而得到下列新
的有序序列,
? {R（ 38）,R（ 49）,R（ 65）,R（ 76）,R（ 97） } (9.4)
? 称从式（ 9.3）到式（ 9.4）的过程为一趟直接插入排序。
? {38,49,65,97} (9.3)
6北京邮电大学自动化学院
? 一般情况下，第 i趟直接插入排序的操作为：
? 在含有 i-1个记录的有序子序列 r[1…i -1]中插入一个记录 r[i]
后，变成含有 i个记录的有序子序序列 r[1…i] ；
? 并且，和顺序查找类似，为了在查找插入位置的过程中避
免数组下标出界，在 r[0]处设置监视哨。
? 整个排序过程为进行 n-1趟插入，即：先将序列中的第一个记
录看成是一个有序序列的子序，然后从第 2个记录起逐个进行
插入直至整个序列变成按关键字非递减有序序列为止。
? 在自 i-1起往前搜索的过程中，可以同时后移记录。
1、直接插入排序
7北京邮电大学自动化学院
例 49 38 65 97 76 13 27
i=2 38 (38 49) 65 97 76 13 27
i=3 65 (38 49 65) 97 76 13 27
i=4 97 (38 49 65 97) 76 13 27
i=5 76 (38 49 65 76 97) 13 27
i=6 13 (13 38 49 65 76 97) 27
i=1 ( )
i=7 (13 38 49 65 76 97) 2727
jj j jjj
977665493827
(13 27 38 49 65 76 97)排序结果：
1、直接插入排序
8北京邮电大学自动化学院 Ch8_1.c
? 当待排序列中记录按关键字非递减有序排列 (正序）所需进行
关键字间比较的次数达最小值
11
2
???
?
nn
i
2
)1)(4()1(
2
?????
?
nnin
i
2
)1)(2(
2
????
?
nnin
i
? 记录移动的次数也达到最大值
? 当待排序列中记录按关键字非递增有序排列（逆序）所需
进行关键字间比较的次数达最大值
? 我们可取上述最小值和最大值的平均值，作为直接插入排序时
所需进行关键字间的比较次数和移动记录的次数，约为 n2/4。
由此，直接插入排序的时间复杂度为 O（ n2）。
? 记录不需要移动。
1、直接插入排序
9北京邮电大学自动化学院
2、其它插入排序
? （ 1）折半插入排序
? 由于插入排序的基本操作是在一个有序表中进行查找和插
入，则从上章的讨论可知，这个“查找”操作可利用“折半
查找”来实现,由此进行的插入排序称之为折半插入排序 。
? 直接插入排序的基本操作是向有序表中插入一个记录，平均情况
下总比较次数约为 n2/4。既然是在有序表中确定插入位置，可以
不断二分有序表来确定插入位置，通过待插入记录与有序表居中
的记录按关键码比较，将有序表一分为二，下次比较在其中一个
有序子表中进行，这样继续下去，直到要比较的子表中只有一个
记录时，比较一次便确定了插入位置。
10北京邮电大学自动化学院
i=1 (30) 13 70 85 39 42 6 20
i=2 13 (13 30) 70 85 39 42 6 20
i=7 6 (6 13 30 39 42 70 85 ) 20
….
i=8 20 (6 13 20 30 39 42 70 85 )
?折半插入排序
i=8 20 (6 13 30 39 42 70 85 ) 20
s jm
i=8 20 (6 13 30 39 42 70 85 ) 20
s jm
i=8 20 (6 13 30 39 42 70 85 ) 20
s jm
i=8 20 (6 13 30 39 42 70 85 ) 20
sj
11北京邮电大学自动化学院
? 算法评价
Ch8_2.c
? 折半插入排序所需附加存储空间和直接插入排序相同，从时
间上比较，折半插入排序仅减少了关键字间的比较次数，而
记录的移动次数不变。因此，折半插入排序的时间复杂度仍
为,O(n2)
? （ 2） 2-路插入排序
? 2路插入排序是在折半排序的基础上再改进之，其目的是减
少排序过程中移动记录的次数，但为此需要 n个记录的辅助
空间。 P267
? 时间复杂度,T(n)=O(n2)
? 空间复杂度,S(n)=O(1)
12北京邮电大学自动化学院
3、希尔排序
? 希尔排序又称“缩小增量法”
? 基本思想,先将整个待排记录序列分割成若干子序列分
别进行直接插入排序，待整个序列中的记录“基本有
序”时，再对全体记录进行一次直接插入排序。
? 排序过程,先取一个正整数 d1<n,把全部记录分成 d1个
组，所 有距离为 d1倍数 的记录放一组，在各组内进行插
入排序；然后取 d2<d1,重复上述分组和排序工作；直至
di=1,即所有记录放进一个组中排序为止。
13北京邮电大学自动化学院
取 d3=1
三趟分组,13 27 48 55 4 49 38 65 97 76
三趟排序,4 13 27 38 48 49 55 65 76 97
例 初始,49 38 65 97 76 13 27 48 55 4
一趟排序,13 27 48 55 4 49 38 65 97 76
二趟排序,13 4 48 38 27 49 55 65 97 76
取 d1=5
一趟分组,49 38 65 97 76 13 27 48 55 4
取 d2=3
二趟分组,13 27 48 55 4 49 38 65 97 76
3、希尔排序
14北京邮电大学自动化学院
Ch8_3.c
例 49 38 65 97 76 13 27 48 55 4
#define T 3
int d[]={5,3,1};
j i
4913 3827
一趟排序,13 27 48 55 4 49 38 65 97 76
j ij i
274
j ij i
55
j i
38
j ij ij i
二趟排序,13 4 48 38 27 49 55 65 97 76
j ij i
6548
j i
9755
j i
764
算法描述
三趟排序,4 13 27 38 48 49 55 65 76 97
15北京邮电大学自动化学院
? 希尔排序的分析是一个复杂的问题，因为它的时间是
所取“增量”序列的函数，这涉及一些数学上尚未解
决的难题。
? 增量序列可以有各种取法，但要注意：应使增量序列
中的值没有除 1之外的公因子，并且最后一个增量值
必须等于 1。
3、希尔排序
? 有人在大量的实验基础上推出：当 n在某个特定范围
内，希尔排序所需的比较和移动次数约为 n1.3，当
n??时，可减少到 n(log2n)2。
16北京邮电大学自动化学院
? 1、起泡排序
9.2 快速排序
? 首先将第一个记录的关键字与第二个记录的关键字进行比较，
若为逆序 r[1].key>r[2].key,则将两个记录交换；
? 然后比较第二个记录与第三个记录的关键字；依次类推，直至
第 n-1个记录和第 n个记录的关键字比较为止。
? 上述过程称作第一趟冒泡排序,其结果使得关键字最大的记录
被安置到最后一个记录的位置上。
? 然后进行第二趟冒泡排序，对前 n-1个记录进行同样操作，其结
果是使关键字次大的记录被安置到第 n-1个记录的位置上。
? ……,重复上述过程，直到“在一趟排序过程中没有进行过交
换记录的操作”为止。
17北京邮电大学自动化学院
例 49
38
65
97
76
13
27
30
初
始
关
键
字
38
49
65
76
13
27
30
97
第
一
趟
38
49
65
13
27
30
76
第
二
趟
38
49
13
27
30
65
第
三
趟
38
13
27
30
49
第
四
趟
13
27
30
38
第
五
趟
13
27
30
第
六
趟
38
49
76
9713
9727
97
13
76
76
7627
30
13
6527
6530
65
13
13
49
4930
4927
3827
3830
38
30
1、起泡排序
18北京邮电大学自动化学院
Ch8_4.c算法描述与分析
? 起泡排序的效率，若初始序列为“正序”，则只需进
行一趟排序，在排序过程中进行 n-1次关键字间的比
较；反之，若初序列“逆序”，则需进行 n-1趟排序，
需进行
2
)1()1(2 ????
?
nni
ni
? 次比较。并作等数量级的记录移动，因此，总的时间
复杂度为 O（ n2）。
19北京邮电大学自动化学院
2、快速排序
? 2、快速排序
? 快速排序 是对起泡排序的一种改进,其基本思想是,通过一
趟排序将待排序记录分割成独立的两部分，其中一部分记录
的关键字均比另一部分记录的关键字小，则可分别对这两部
分记录进行排序，以达到整个序列有序。
? 假设待排序的序列为 {L.r[s],L.r[s+1],…, L.r[t]}，首先任
意选取一个记录（通常可选第一个记录 L.r[s]）作为 枢轴 （或
支点 Pivot），然后按下述原则重新排列其余记录：将所有关
键字较它小的记录都安置在它的位置之前，将所有关键字较
它大的记录都安置在它的位置之后。
20北京邮电大学自动化学院
? 由此，可以该,枢轴,记录最后所落的位置最作分界线，将
序列 {L.r[s],L.r[s+1],…, L.r[t]}分割成两个子序列
{L.r[s],L.r[s+1],…, L.r[i-1]}和 {L.r[i+1],L.r[i+2],…,
L.r[t]},这个过程称作一趟快速排序 。
? 一趟快速排序的具体做法是,对 r[s……t] 中记录进行一趟快
速排序，附设两个指针 low和 high，它们的初值分别为 low和
high,设枢轴记录的关键字为 Pivotkey，
? 然后从 low所指位置起向后搜索找到第一个关键字大于
Pivotkey的记录和 枢轴记录相互交换 做，重复这两步直至
low=high。
? 首先从 high所指位置起向前搜索找到第一个关键字小于
Pivotkey的记录和 枢轴记录相互交换，
快速排序
21北京邮电大学自动化学院
初始关键字,49 38 65 97 76 13 27 50
i j
x
ji
完成一趟排序,( 27 38 13) 49 (76 97 65 50)
分别进行快速排序,( 13) 27 (38) 49 (50 65) 76 (97)
快速排序结束,13 27 38 49 50 65 76 97
4927
i ji ji j
49 65
ji
13 49
i j
49 97
ij
快速排序实例
22北京邮电大学自动化学院 Ch8_5.c
? 通常，快速排序平均时间复杂度为 O(nlogn)，但待排序记录的
键值几乎已排序时，情况反而恶化，每一趟快速快速排序的基
准记录位置就是第一个记录位置或最后一个记录位置。 最坏情
况下的时间复杂度为 T(n)=O(n2)。
? 快速排序的平均时间为 Tavg(n)=knlnn，其中 n为待排序序列记
录的个数,k为某个常数，经验证明，在所有同数量级的此类
（先进的）排序方法中，快速排序的常数因子 k最小。因此，
就平均时间而言，快速排序是目前被认为是最好的一种内部排
序方法。
? 快速排序递归算法需要栈空间来实现递归，一般情况下需要的空
间为 S(n)=O(log2n)，最坏情况下，需要的栈空间为 S(n)=O(n)。
? 快速排序方法是不稳定的 。
快速排序
23北京邮电大学自动化学院
? 选择排序的基本思想,每一趟在 n-i+1(i =1,2,…,n -1)个记录
中选取关键字最小的记录作为有序序列中第 i 个记录。
9.3 选择排序
? 1、简单选择排序
? 一趟简单选择排序的操作为：通过 n-1次关键字的比较，从
n- i +1个记录中选择出关键字最小的记录，并和第 i（ 1?i?
n）个记录 交换之。
? 再通过 n-2次比较，从剩余的 n-1个记录中找出关键字次小
的记录，将它与第二个记录交换
? 重复上述操作，共进行 n-1趟排序后，排序结束,
24北京邮电大学自动化学院
初始,[ 49 38 65 97 76 13 27 ]
k
j j j j j j
k k
i=1 13 49
一趟,13 [38 65 97 76 49 27 ]i=2
k k
j j j jj
27 38
二趟,13 27 [65 97 76 49 38 ]
三趟,13 27 38 [97 76 49 65 ]
四趟,13 27 38 49 [76 97 65 ]
五趟,13 27 38 49 65 [97 76 ]
六趟,13 27 38 49 65 76 [97 ]
排序结束,13 27 38 49 65 76 97
1、简单选择排序
25北京邮电大学自动化学院
? 简单选择排序过程中，所需进行记录移动的操作次数较少，
其最小值为,0”，最大值为 3(n-1)。然而，无论记录的初始
排列如何，所需进行的关键字间的比较次数相同，均为 (n(n-
1)/2。因此，总的时间复杂度也是 O（ n2）。
算法描述与算法评价 Ch8_6.c
? 从上述可见，选择排序的主要操作是进行关键字间的比较，
因此改进简单选择排序应从如何减少“比较”出发考虑。显
然，在 n个关键字中选出最小值，至少进行 n-1次比较，然
而，继续在剩余的 n-1个关键字中选择小值就并非一定要进行
n-2次比较，若能利用前 n-1次比较所得信息，则可减少以后
各趟选择排序中所用的比较次数。
26北京邮电大学自动化学院
2、树形选择排序
? 树形选择排序，又称锦标赛排序,是一种按照锦标赛
的思想进行选择排序的方法。
? 首先对 n个记录的关键字进行两两比较，然后在其中 ?n/2?
个较小者之间再进行两两比较，如此重复，直至选出最小
关键字的记录为止。
? 这个过程可用一棵有 n个叶子结点的完全二叉树表示,8个
叶子结点中依次存放排序之前的 8个关键字,每个非终端结
点中的关键字均等于其左、右孩子结点中较小的关键字，
则根结点中的关键字即为叶子结点中的最小关键字 。
27北京邮电大学自动化学院
? 在输出最小关键字之后，根据关系的可传递性，欲选出
次小关键字，仅需要将叶子结点中的最小关键字改为
“最大值”，然后从该叶子结点开始，和其左（右）兄
弟的关键字进行比较,修改从叶子结点到根的路径上各
结点的关键字，则根结点的关键字即为次小关键字 。
? 同理可依次从小到大的所有关键字。由于含有 n个叶子结
点的完全二叉树的深度为 ?log2n+1?，则在树形选择中，
除了最小关键字之外，每选择一个次小关键字仅需进行
?log2n?次比较，因此，它的时间复杂度为 O（ nlog2n)。
2、树形选择排序
28北京邮电大学自动化学院
38 6549 97 76 13 27 49
38 65 13 27
38 13
13
38 6549 97 76 ? 27 49
38 65 76 27
38 27
27
38 6549 97 76 ? ? 49
38 65 76 49
38 49
38
树形选择排序示例
输出 13之后
输出 13,27之后
29北京邮电大学自动化学院
或 (i=1,2,…..,?n/2?)ki?k2ik
i?k2i+1
ki?k2i
ki?k2i+1
3、堆排序
? 堆排序只需要一个记录大小的辅助空间，每个待排序的记录
仅占有一个存储空间。
? （ 2）堆和完全二叉树 若将和此序列对应的一维数组
（即以一维数组作此序列的存储结构）看成是一个完全二叉
树，则堆的含义表明，完全二叉树中所有非终端点的值均不
大于（或不小于）左、右孩子结点的值。由此，若序列 {k1,
k2,……k n}是堆，则堆顶元素（或完全二叉树的根）必为序
列中 n个元素的最小值（或最大值）
? （ 1）堆的定义, n个元素的序列 (k1,k2,……k n),当且仅当满
足下列关系时，称之为堆
30北京邮电大学自动化学院
例 （ 96,83,27,38,11,9）
例 （ 13,38,27,50,76,65,49,97）
96
27
91138
83
13
2738
49657650
97
? 可将堆序列看成完全二叉树，则堆顶元素
（完全二叉树的根）必为序列中 n个元素的最
小值或最大值
3、堆排序
31北京邮电大学自动化学院
? （ 3）堆排序,若在输出堆顶的最小值之后，使得剩余
n-1个元素的序列重又建成一个堆，则可得到 n个元素的
次小值；如此反复执行，便能得到一个有序序列，这个
过程称之为 堆排序 。
? 实现堆排序需解决的两个问题
? 如何由一个无序序列建成一个堆？
? 如何在输出堆顶元素之后，调整剩余元素，使之
成为一个新的堆？
? 二个问题解决方法 —— 筛选
3、堆排序
32北京邮电大学自动化学院
? （ 4）筛选
? 方法：
? 输出堆顶元素之后，以堆中最后一个元素替代之；
? 然后将根结点值与左、右子树的根结点值进行比较，并
与其中小者进行交换；
? 重复上述操作，直至叶子结点，将得到新的堆,称这个
从堆顶至叶子的调整过程为“筛选”
3、堆排序
33北京邮电大学自动化学院
例 13
2738
49657650
97
97
2738
49657650
13
输出,13
27
4938
97657650
13
输出,13
97
4938
27657650
13
输出,13 27
38
4950
27657697
13
输出,13 27
65
4950
27387697
13
输出,13 27 38
3、堆排序
34北京邮电大学自动化学院
49
6550
27387697
13
输出,13 27 38
76
6550
27384997
13
输出,13 27 38 49
50
6576
27384997
13
输出,13 27 38 49
97
6576
27384950
13
输出,13 27 38 49 50
65
9776
27384950
13
输出,13 27 38 49 50
97
6576
27384950
13
输出,13 27 38 49 50 65
3、堆排序
35北京邮电大学自动化学院
76
6597
27384950
13
输出,13 27 38 49 50 65
97
6576
27384950
13
输出,13 27 38 49 50 65 76
97
6576
27384950
13
输出,13 27 38 49 50 65 76 97
3、堆排序
36北京邮电大学自动化学院
? （ 5）建堆
? 从一个无序序列建堆的过程就是一个反复“筛选”的过
程，若将此序列看成是一个完全二叉树，则最后一个非
终端结点是 ?n/2?个元素，由此“筛选”只需从 ?n/2?个
元素开始。
? 建堆,从无序序列的第 ?n/2?个元素（即此无序序列对
应的完全二叉树的最后一个非终端结点）起，至第一个
元素止，进行反复筛选
3、堆排序
37北京邮电大学自动化学院
49
6538
27137697
50
49
6538
27137650
97
49
1338
27657650
97
49
1338
27657650
97
13
2738
49657650
97
例如 含 8个元素的无序序列
（ 49,38,65,97,76,13,27,50）
3、堆排序
38北京邮电大学自动化学院
Ch8_7.c
? 时间复杂度,最坏情况下 T(n)=O(nlogn)
? 空间复杂度,S(n)=O(1)
? 因为其运行时间主要耗费在建初始堆和调整新建堆时进行的
反复“筛选”上。对深度为 k的堆，筛选算法中进行的关键
字比较次数至多为 2(k-1)次。总共进行的比较的次数为：
<2(?log2(n-1)?+ ?log2(n-2)?+……+log 22))<2n(?log2n?)由
此,堆排序在最坏的情况下，其时间复杂度为 O(nlogn)。
? 相对于快速排序，此外，堆排序仅需一个记录大小供交换
用,…… 。因此是一种适合于排序较大文件的排序方法。
? 堆排序是一种不稳定的排序方法。
3、堆排序
39北京邮电大学自动化学院
? 归并排序 是又一类不同的排序方法。“归并”的含义是将两
个或两个以上的有序表组合成一个新的有序表
9.4 归并排序
? 排序过程,假设初始序列含有 n个记录，则可看成 n个有序
的子序列，每个子序列长度为 1，然后两两归并，得到 ?n/2?
个长度为 2或 1的有序子序列；再两两归并,…… 如此重复，
直至得到一个长度为 n的有序序列为止，这种排序方法称为
2-路归并排序。
? 2-路归并排序中的核心操作是将一维数组中前后相邻的两个
有序序列归并为一个有序序列。 —— 将两个或两个以上的
有序表组合成一个新的有序表，叫 2-路归并排序。
40北京邮电大学自动化学院
初始关键字,[49] [38] [65] [97] [76] [13] [27]
一趟归并后,[38 49] [65 97] [13 76] [27]
二趟归并后,[38 49 65 97] [13 27 76]
三趟归并后,[13 27 38 49 65 76 97]
归并排序
41北京邮电大学自动化学院
? 时间复杂度,T(n)=O(nlog2n)
Ch8_9.c
? 空间复杂度,S(n)=O(n)
? 一趟归并排序的操作是,调用 ? ?次算法将 SR[1,…,n] 中
前后相邻且长度为 h的有序序列段进行两两归并，得到前后
相邻、长度为 2h 的有序段，并存放在 TR[1,…,n] 中，整个归
并排序需进行 ?log2n?趟。可见，实现归并排序需和待排序记
录等数量的辅助空间，其时间复杂度为 O(nlog2n)。
? 与快速排序和堆排序相比，归并排序的最大特点，它是一种
稳定的排序方法 。但在一般情况下，很少利用 2路归并排序
方法进行内部排序。
h
n
2
归并排序
42北京邮电大学自动化学院
? ?2<?3<……< ?A<?2<?3<……< ?A<
? ?2<?3<……< ?A<?2<?3<……< ?A
9.5 基数排序
? 1、多关键字排序
? 每一张牌有两个“关键字”,花色和面值,且“花色”的地
位高于“面值”，在比较任意两张牌面的大小时，必须先比
较“花色”，若“花色”相同，则再比较面值。
? 已知扑克牌中 52张牌面的次序为：
? 两个关键字,花色（ ?<?<?<?）
面值（ 2<3<……<A ）
? 并且“花色”地位高于“面值”
43北京邮电大学自动化学院
? 方法 1,先对花色排序，将其分为 4个组，即梅花组、方块
组、红心组、黑心组。再对每个组分别按面值进行排序，
最后，将 4个组连接起来即可。
? 方法 2,先按 13个面值给出 13个编号组 (2号,3号,...,A
号 )，将牌按面值依次放入对应的编号组，分成 13堆。再按
花色给出 4个编号组 (梅花、方块、红心、黑心 )，将 2号组中
牌取出分别放入对应花色组，再将 3号组中牌取出分别放入
对应花色组,……,这样,4个花色组中均按面值有序，然
后，将 4个花色组依次连接起来即可。
? 由此，将扑克牌调整成如上所述次序时，通常采用的方法是：
1、多关键字排序
44北京邮电大学自动化学院
? 一般情况下，假设有 n个记录的序列 {R1,R2,…, Rn}，且每
个记录 Ri中含有 d个关键字（ Ki0,Ki1,…, Kid-1），则称序列
对关键字（ K0,K1,…, Kd-1）有序是指：对于序列中任意两
个记录 Ri和 Rj（ 1? i<j?n）都满足下列有序关系
? 为实现多关键字排序，通常有两种方法：
? 先对 最高位关键字进行排序
? 先对 最高低关键字进行排序
? （ Ki0,Ki1,…, Kid-1） <（ Kj0,Kj1,…, Kjd-1）
? 其中 K0称为 最主位关键字, Kd-1称为 最次位关键字 。
1、多关键字排序
45北京邮电大学自动化学院
? 第一种方法是先对最高位关键字 K0（ 如花色）进行排序，
将序列分成若干子序列，每个子序列中的记录都具有相同
的 K0值；
? 然后分别就每个子序列对次关键字 K1（ 如面值）进行排
序，按 K1值不同再 分成若干更小的子序列；
? 依次重复，直至对 Kd-2进行排序之后得到的每一子序列中
的记录都具有相同的关键字（ K0,K1,…, Kd-2），而后
分别每个子序列对 Kd-1进行排序，最后将所有子序列依次
联接在一起成为一个有序序列，这种方法称之为 最高优先
法（ Most Significant Digit first） （ MSD) 。
1、多关键字排序
46北京邮电大学自动化学院
? 第二种方法是从最低位关键字 Kd-1起进行排序。然后再对高
一位的关键字 Kd-2排序,…… 依次重复，直至对最高位关键
字 K0排序后，便成为一个有序序列。这种方法称之为 最低
位优先法 (LSD)。
? MSD与 LSD不同特点
? 按 MSD排序,必须将序列逐层分割成若干子序
列，然后对各子序列分别排序 。
? 按 LSD排序,不必分成子序列，对每个关键字都是
整个序列参加排序；并且可不通过关键字比较，而
通过若干次, 分配, 与, 收集, 实现排序 。
1、多关键字排序
47北京邮电大学自动化学院
2、链式基数排序
? 基数排序,借助“分配”和“收集”对单逻辑关键字进行排
序的一种方法
? 链式基数排序,用链表作存储结构的基数排序
? 逻辑关键字可以看成由若干个关键字复合而成的。例如，若
关键字是数值，且其值都在 0?k?999范围内，则可把每一个
十进制数字看成一个关键字，即可认为 K由三个关键字
（ K0,K1,K2 ）组成，其中 K0是百位数,K1是十位数，
K2是个位数；
? 又若关键字 K由五个字母组成的单词，则可看成是由五个关
键字（ （ K0,K1,K2, K3,K4 ）组成，其中 K j-1是（自
左至右）的第 j+1个字母。
48北京邮电大学自动化学院
? 由于如此分解而得的每个关键字 Kj都在相同的范围内
（对数字,0?Kj?9，对字母,A”?Kj?‘Z”），按 LSD进
行排序更为方便，只要从最小数位关键字起，按关键字
的不同值将序列中记录“分配”到 RADIX个队伍中后再
“收集”之，如此重复 d次。
? 按这种方法实现排序称之为基数排序,其中“基”指的
是 RADIX的取值范围，在上述两种关键字的情况下，它
们分别是,10”和,26”。
? 首先以静态链表存储 n个待排记录，并令表头指针指向第
一个记录，如图 (a)所示。
2、链式基数排序
49北京邮电大学自动化学院
? 第一趟分配对最低数位关键字（个位数）进行，改变记录
的指针值将链表中的记录分配至 10个链对列中去，每个队
列中的记录关键字的个位数相等，如图 (b)所示。
? 其中 f[i]和 e[i]分别为第 i个队列的头指针和尾指针；
? 第一趟收集是改变所有非空队列的对尾记录的指针值域，
令其指向下一个非空队列的对头的记录，重新将 10个队列
中的记录链成一个链表，如图（ c）所示；
? 第二趟分配，第二趟收集及第三趟分配和第三趟收集分别
是对十位数和百位数进行的，其过程和个位数相同，如图
(d)~(g)所示，至此排序完毕。
2、链式基数排序
50北京邮电大学自动化学院
例 初始状态：
278 109 063 930 589 184 505 269 008 083
109
589
269
278063930
083
184 505
008
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
一
趟
分
配
930 063 083 184 505 278 008 109 589 269
一趟收集：
2、链式基数排序
51北京邮电大学自动化学院
505 008 109 930 063 269 278 083 184 589
二趟收集：
083
184
589
063505
269
930
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
二
趟
分
配
008
109
278
930 063 083 184 505 278 008 109 589 269
一趟收集,2、链式基数排序
52北京邮电大学自动化学院
008 063 083 109 184 269 278 505 589 930
三趟收集：
109008
184
930
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
三
趟
分
配
063
083
269
278
505
589
505 008 109 930 063 269 278 083 184 589
二趟收集,2、链式基数排序
53北京邮电大学自动化学院
Ch8_10.c
? 算法评价
? 时间复杂度：分配,T(n)=O(n)
? 收集,T(n)=O(rd)
? T(n)=O(d(n+rd))
? 空间复杂度, S(n)=2rd个队列指针 。 +n个指针域空间
? 对于 n个记录（假设每个记录含有 d个关键字，每个关键字的
取值范围为 rd个值，进行链式基数排序的时间复杂度为
O(d(n+rd))，其中每一趟分配的时间复杂度为 O(n)，每一趟收
集的时间复杂度为 O(rd)，整个排序需进行 d趟分配和收集。
2、链式基数排序
? 其中：
? n—— 记录数
? d—— 关键字数
? rd—— 关键字取值范围
54北京邮电大学自动化学院
9.6 各种内部排序方法的比较讨论
排序方法 平均时间 最坏情况 辅助存储
简单排序 O(n2) O(n2) O(1)
快速排序 O(nlogn) O(n2) O(logn)
堆排序 O(nlogn) O(nlogn) O(1)
归并排序 O(nlogn) O(nlogn) O(n)
基数排序 O(n(d+rd)) O(n(d+rd)) O(rd)
55北京邮电大学自动化学院
? 从上表可以得出如下结论：
? （ 1） 从平均时间性能而言，快速排序最佳，其所需时间最
省,但快速排序在最坏情况下的时间性能不如堆排序和归
并排序。而后两者相比较的结果是，在 n较大时，归并排序
所需时间较堆排序省，但它所需的辅助存储量最多。
? （ 2）上表中的“简单排序”包括除希尔排序之外的所有插
入排序，起泡排序和简单选择排序，其中以直接插入排序
为最简单,当序列中的记录“基本有序”或 n值较小时，它
是最佳的排序方法,因此常将它和其它的排序方法，诸如
快速排序、归并排序等结合起来使用。
9.6 各种内部排序方法的比较讨论
56北京邮电大学自动化学院
? （ 3）基数排序的时间复杂度也可写成 O(nd)。因此，它
最适合用于 n值很大而关键字较小的序列。若关键字也很
大，而序列中大多数记录的“最高位关键字”均不同，则
也可先按“最高位关键字”不同将序列分成若干“小”的
子序列，而后进行直接插入排序。
? （ 4）从方法的稳定性来比较，基数排序是稳定的内排方
法，所有时间复杂度为 O(n2)的简单排序也是稳定的，然
而,快速排序、堆排序和希尔排序等时间性能较好的排序
方法都是不稳定的。
9.6 各种内部排序方法的比较讨论
57北京邮电大学自动化学院
? 一、单项选择题
? 1、排序方法中，从未排序序列中依次取出元素与已排序序
列（初始时为空）中的元素进行比较，将其放入已排序序列
的正确位置上的方法，称为
? （ A）希尔排序 （ B）冒泡排序
? （ C）插入排序 （ D）选择排序
? 2、在文件“局部有序”或文件长度较小的情况下，最佳内
排序方法是
? （ A）直接插入排序 （ B）冒泡排序
? （ C）直接选择排序 （ D）归并排序
第 9章 作业
58北京邮电大学自动化学院
? 3、对给出的一组关键字 {14,5,19,20,11,19}。若按关
键字非递减排序，第一趟排序结果为 {14,5,19,20,11，
19}，问采用的排序算法是
? （ A）简单选择排序 （ B）快速排序
? （ C）希尔排序 （ D）二路归并排序
? 4、在所有排序方法中，关键字比较的次数与记录的初始排
列次序无关的是
? （ A）希尔排序 （ B）冒泡排序
? （ C）插入排序 （ D）选择排序
第 9章 作业
59北京邮电大学自动化学院
? 二、填空题
? 1、在对一组记录 {54,38,96,23,15,72,60,45,83}
进行直接插入排序时，当把第 7个记录 60插入到有序表时，
为寻找插入位置需比较 次。
? 2、每次直接或通过基准元素间接比较两个元素，若出现逆序
排列时就交换它们的位置，此种排序方法叫做 排序；
每次使两个相邻的有序表合并成一个有序表的排序方法叫做
排序。
? 3,排序方法采用的是二分法的思想,排序方
法其数据的组织采用完全二叉树结构。
第 9章 作业
60北京邮电大学自动化学院
? 1、对于给定的键值序列 {12,2,16,30,8,28,4,10}
分别写出直接插入排序、折半插入排序、希尔排序、直接
选择排序、起泡排序的过程，并算出比较和记录移动次
数。
? 2、对于给定的键值序列 {41,62,13,84,35,96，
57,39,79,61,15,83}，分别写出快速排序、归并排
序、堆排序的各趟排序结果。
? 3、本章介绍的内部排序方法中，哪几种是稳定的？哪几
种是不稳定的？
第 9章 作业
61北京邮电大学自动化学院
第 9章 上机实习题
? 基本要求
? （ 1）选顺序存储结构存放待排序的记录。输入并存放 n个
待排序的记录
? （ 2）分别用堆排序、快速排序和归并排序方法，对待排
序记录进行排序并输出排序结果。
62北京邮电大学自动化学院
,数据结构, 考试题型
?一、填空题（ 10分）
?二、判断题（共 10分）
?三、单项选择题（共 20分，其中程序题 6分）
?四、作图题（ 6分）
?五、程序填空题 (共 18分 )
?六、简答题（ 12分）
?七、简答题 （ 12分）
?八、简答题（ 12分）
63北京邮电大学自动化学院
?一、填空题（将正确答案填在相应的空中，每题
1.5分，共 9分）
?二、判断下列陈述是否正确，正确时记为
,∨,，错误时则为,×,。（每小题 1分，共 10
分）
?1、设三角矩阵为采用压缩存储。已知 a11地址为
1,a43的存储地址是。
?1、如果某种排序算法是不稳定的，则该方法没有
实际实用价值。
,数据结构, 考试试题
64北京邮电大学自动化学院
?三、单项选择题（每小题 1.5分，共 15分，其中程
序题 6分）
?1、设有一个空栈，栈顶指针为 1000H（十六进
制，下同），现有输入序列为 1,2,3,4,5，
经过 PUSH,PUSH,POP,PUSH,POP，
PUSH,PUSH后，输出序列是,栈顶指针
是 。
?① 5,4,3,2,1 ② 2,1 ③ 2,3
④ 3,4 ⑤ 1002H ⑥ 1004H
⑦ 1005H ⑧ 1003H
,数据结构, 考试试题
65北京邮电大学自动化学院
? 简答题：对于给定的键值序列 {12,2,16,30,8,28，
4,10}分别写出直接插入排序、折半插入排序、希尔排
序、直接选择排序、起泡排序的过程，并算出比较和记录
移动次数。
第 9章 作业
第 9章 排序
? 9.1 概述 ? 1、排序
? 排序 是计算机程序设计中的一种重要操作，它的功能是将一个
数据元素（或记录）的任意序列，重新排列成一个按关键字有
序序列。
? 其相应的关键字序列为
? {K1,K2,……, K n}，
? 假设含 n个记录的序列为：
? {R1,R2,……, R n} (9.1）
? 需确定 1,2,……, n的一种排列 P1,P2,……, P n，使其相
应的关键字满足如下的非递减（或非递增）关系
KP1?KP2?…… ?KP n，即使（ 9.1）式的序列成为一个按关键字
有序的序列 {RP1,RP2,……, RPn}，这样一种操作称为 排序 。
2北京邮电大学自动化学院
? 2、稳定的、非稳定的
? 3、内部排序、外部排序
? 假设 Ki=Kj（ 1 ? i ? n,1 ? j ? n,i?j）且在排序前的序列中
Ri领先 Rj（即 i<j）。
? 内部排序,指的是待排序记录存放在计算机随机存储器中
进行的排序过程。
? 外部排序,指的是排序记录的数量很大，以致内存一次
不能容纳全部记录，在排序过程中尚需对外存进行访问
的排序过程。
? 反之，若可能使排序后的序列中 Rj领先于 Ri，则称所用的
排序方法是 不稳定的 。
? 若在排序后的序列中 Ri仍领先 Rj，则称所用的排序方法是 稳
定的 ；
3北京邮电大学自动化学院
? 4、排序方法
? 插入排序,直接插入排序、折半插入排序、希尔排序
? 交换排序,冒泡排序、快速排序
? 选择排序,简单选择排序、树形选择排序、堆排序
? 归并排序, 2-路归并排序
? 基数排序, 多关键字排序、链式基数排序
? 如果按内部排序过程中所需的工作量来区分，可分为：
? （ 1）简单排序,其时间复杂度为 T(n)=O(n2)
? （ 2） 先进的排序方法, 其时间复杂度为 T(n)=O(nlogn)
? （ 3） 基数排序, 其时间复杂度为 T(n)=O(d.n)
? 5,排序基本操作,
? （ 1）比较两个关键字大小；
? （ 2）将记录从一个位置移动到另一个位置。
4北京邮电大学自动化学院
? 插入排序的基本思想是,每一步将一个待排序的记录，按
其主关键字的大小插入到前面已经排序的文件中适当位置
上，直至全部插完为止。
9.1 插入排序
? 1、直接插入排序
? 直接插入排序是一种最简单的排序方法，它的基本操作
是将一个记录插入到已排好的有序表中，从而得到一个
新的、记录数增加 1的有序表。
? 例如：已知待排序的一组记录的初始排列如下所示,R
（ 49）,R（ 38）,R（ 65）,R（ 97）,R（ 76）,R
（ 13）,R（ 27）,R（ 19）。
5北京邮电大学自动化学院
1、直接插入排序
? 假设在排序过程中，前四个记录已按关键字递增的次序，重
新排列，构成一个含 4个记录的有序序列,
? 现要将第 5个（关键字为 76）的记录插入上述序列，可以得
到一个新的含 5个记录的有序序列,则首先要找到插入的位
置，然后进行插入。
? 假设从 R（ 97）起向左进行顺序查找，由于 65 ?76 ? 97，则
R（ 76）应插入在 R（ 65）和 R（ 97）之间，从而得到下列新
的有序序列,
? {R（ 38）,R（ 49）,R（ 65）,R（ 76）,R（ 97） } (9.4)
? 称从式（ 9.3）到式（ 9.4）的过程为一趟直接插入排序。
? {38,49,65,97} (9.3)
6北京邮电大学自动化学院
? 一般情况下，第 i趟直接插入排序的操作为：
? 在含有 i-1个记录的有序子序列 r[1…i -1]中插入一个记录 r[i]
后，变成含有 i个记录的有序子序序列 r[1…i] ；
? 并且，和顺序查找类似，为了在查找插入位置的过程中避
免数组下标出界，在 r[0]处设置监视哨。
? 整个排序过程为进行 n-1趟插入，即：先将序列中的第一个记
录看成是一个有序序列的子序，然后从第 2个记录起逐个进行
插入直至整个序列变成按关键字非递减有序序列为止。
? 在自 i-1起往前搜索的过程中，可以同时后移记录。
1、直接插入排序
7北京邮电大学自动化学院
例 49 38 65 97 76 13 27
i=2 38 (38 49) 65 97 76 13 27
i=3 65 (38 49 65) 97 76 13 27
i=4 97 (38 49 65 97) 76 13 27
i=5 76 (38 49 65 76 97) 13 27
i=6 13 (13 38 49 65 76 97) 27
i=1 ( )
i=7 (13 38 49 65 76 97) 2727
jj j jjj
977665493827
(13 27 38 49 65 76 97)排序结果：
1、直接插入排序
8北京邮电大学自动化学院 Ch8_1.c
? 当待排序列中记录按关键字非递减有序排列 (正序）所需进行
关键字间比较的次数达最小值
11
2
???
?
nn
i
2
)1)(4()1(
2
?????
?
nnin
i
2
)1)(2(
2
????
?
nnin
i
? 记录移动的次数也达到最大值
? 当待排序列中记录按关键字非递增有序排列（逆序）所需
进行关键字间比较的次数达最大值
? 我们可取上述最小值和最大值的平均值，作为直接插入排序时
所需进行关键字间的比较次数和移动记录的次数，约为 n2/4。
由此，直接插入排序的时间复杂度为 O（ n2）。
? 记录不需要移动。
1、直接插入排序
9北京邮电大学自动化学院
2、其它插入排序
? （ 1）折半插入排序
? 由于插入排序的基本操作是在一个有序表中进行查找和插
入，则从上章的讨论可知，这个“查找”操作可利用“折半
查找”来实现,由此进行的插入排序称之为折半插入排序 。
? 直接插入排序的基本操作是向有序表中插入一个记录，平均情况
下总比较次数约为 n2/4。既然是在有序表中确定插入位置，可以
不断二分有序表来确定插入位置，通过待插入记录与有序表居中
的记录按关键码比较，将有序表一分为二，下次比较在其中一个
有序子表中进行，这样继续下去，直到要比较的子表中只有一个
记录时，比较一次便确定了插入位置。
10北京邮电大学自动化学院
i=1 (30) 13 70 85 39 42 6 20
i=2 13 (13 30) 70 85 39 42 6 20
i=7 6 (6 13 30 39 42 70 85 ) 20
….
i=8 20 (6 13 20 30 39 42 70 85 )
?折半插入排序
i=8 20 (6 13 30 39 42 70 85 ) 20
s jm
i=8 20 (6 13 30 39 42 70 85 ) 20
s jm
i=8 20 (6 13 30 39 42 70 85 ) 20
s jm
i=8 20 (6 13 30 39 42 70 85 ) 20
sj
11北京邮电大学自动化学院
? 算法评价
Ch8_2.c
? 折半插入排序所需附加存储空间和直接插入排序相同，从时
间上比较，折半插入排序仅减少了关键字间的比较次数，而
记录的移动次数不变。因此，折半插入排序的时间复杂度仍
为,O(n2)
? （ 2） 2-路插入排序
? 2路插入排序是在折半排序的基础上再改进之，其目的是减
少排序过程中移动记录的次数，但为此需要 n个记录的辅助
空间。 P267
? 时间复杂度,T(n)=O(n2)
? 空间复杂度,S(n)=O(1)
12北京邮电大学自动化学院
3、希尔排序
? 希尔排序又称“缩小增量法”
? 基本思想,先将整个待排记录序列分割成若干子序列分
别进行直接插入排序，待整个序列中的记录“基本有
序”时，再对全体记录进行一次直接插入排序。
? 排序过程,先取一个正整数 d1<n,把全部记录分成 d1个
组，所 有距离为 d1倍数 的记录放一组，在各组内进行插
入排序；然后取 d2<d1,重复上述分组和排序工作；直至
di=1,即所有记录放进一个组中排序为止。
13北京邮电大学自动化学院
取 d3=1
三趟分组,13 27 48 55 4 49 38 65 97 76
三趟排序,4 13 27 38 48 49 55 65 76 97
例 初始,49 38 65 97 76 13 27 48 55 4
一趟排序,13 27 48 55 4 49 38 65 97 76
二趟排序,13 4 48 38 27 49 55 65 97 76
取 d1=5
一趟分组,49 38 65 97 76 13 27 48 55 4
取 d2=3
二趟分组,13 27 48 55 4 49 38 65 97 76
3、希尔排序
14北京邮电大学自动化学院
Ch8_3.c
例 49 38 65 97 76 13 27 48 55 4
#define T 3
int d[]={5,3,1};
j i
4913 3827
一趟排序,13 27 48 55 4 49 38 65 97 76
j ij i
274
j ij i
55
j i
38
j ij ij i
二趟排序,13 4 48 38 27 49 55 65 97 76
j ij i
6548
j i
9755
j i
764
算法描述
三趟排序,4 13 27 38 48 49 55 65 76 97
15北京邮电大学自动化学院
? 希尔排序的分析是一个复杂的问题，因为它的时间是
所取“增量”序列的函数，这涉及一些数学上尚未解
决的难题。
? 增量序列可以有各种取法，但要注意：应使增量序列
中的值没有除 1之外的公因子，并且最后一个增量值
必须等于 1。
3、希尔排序
? 有人在大量的实验基础上推出：当 n在某个特定范围
内，希尔排序所需的比较和移动次数约为 n1.3，当
n??时，可减少到 n(log2n)2。
16北京邮电大学自动化学院
? 1、起泡排序
9.2 快速排序
? 首先将第一个记录的关键字与第二个记录的关键字进行比较，
若为逆序 r[1].key>r[2].key,则将两个记录交换；
? 然后比较第二个记录与第三个记录的关键字；依次类推，直至
第 n-1个记录和第 n个记录的关键字比较为止。
? 上述过程称作第一趟冒泡排序,其结果使得关键字最大的记录
被安置到最后一个记录的位置上。
? 然后进行第二趟冒泡排序，对前 n-1个记录进行同样操作，其结
果是使关键字次大的记录被安置到第 n-1个记录的位置上。
? ……,重复上述过程，直到“在一趟排序过程中没有进行过交
换记录的操作”为止。
17北京邮电大学自动化学院
例 49
38
65
97
76
13
27
30
初
始
关
键
字
38
49
65
76
13
27
30
97
第
一
趟
38
49
65
13
27
30
76
第
二
趟
38
49
13
27
30
65
第
三
趟
38
13
27
30
49
第
四
趟
13
27
30
38
第
五
趟
13
27
30
第
六
趟
38
49
76
9713
9727
97
13
76
76
7627
30
13
6527
6530
65
13
13
49
4930
4927
3827
3830
38
30
1、起泡排序
18北京邮电大学自动化学院
Ch8_4.c算法描述与分析
? 起泡排序的效率，若初始序列为“正序”，则只需进
行一趟排序，在排序过程中进行 n-1次关键字间的比
较；反之，若初序列“逆序”，则需进行 n-1趟排序，
需进行
2
)1()1(2 ????
?
nni
ni
? 次比较。并作等数量级的记录移动，因此，总的时间
复杂度为 O（ n2）。
19北京邮电大学自动化学院
2、快速排序
? 2、快速排序
? 快速排序 是对起泡排序的一种改进,其基本思想是,通过一
趟排序将待排序记录分割成独立的两部分，其中一部分记录
的关键字均比另一部分记录的关键字小，则可分别对这两部
分记录进行排序，以达到整个序列有序。
? 假设待排序的序列为 {L.r[s],L.r[s+1],…, L.r[t]}，首先任
意选取一个记录（通常可选第一个记录 L.r[s]）作为 枢轴 （或
支点 Pivot），然后按下述原则重新排列其余记录：将所有关
键字较它小的记录都安置在它的位置之前，将所有关键字较
它大的记录都安置在它的位置之后。
20北京邮电大学自动化学院
? 由此，可以该,枢轴,记录最后所落的位置最作分界线，将
序列 {L.r[s],L.r[s+1],…, L.r[t]}分割成两个子序列
{L.r[s],L.r[s+1],…, L.r[i-1]}和 {L.r[i+1],L.r[i+2],…,
L.r[t]},这个过程称作一趟快速排序 。
? 一趟快速排序的具体做法是,对 r[s……t] 中记录进行一趟快
速排序，附设两个指针 low和 high，它们的初值分别为 low和
high,设枢轴记录的关键字为 Pivotkey，
? 然后从 low所指位置起向后搜索找到第一个关键字大于
Pivotkey的记录和 枢轴记录相互交换 做，重复这两步直至
low=high。
? 首先从 high所指位置起向前搜索找到第一个关键字小于
Pivotkey的记录和 枢轴记录相互交换，
快速排序
21北京邮电大学自动化学院
初始关键字,49 38 65 97 76 13 27 50
i j
x
ji
完成一趟排序,( 27 38 13) 49 (76 97 65 50)
分别进行快速排序,( 13) 27 (38) 49 (50 65) 76 (97)
快速排序结束,13 27 38 49 50 65 76 97
4927
i ji ji j
49 65
ji
13 49
i j
49 97
ij
快速排序实例
22北京邮电大学自动化学院 Ch8_5.c
? 通常，快速排序平均时间复杂度为 O(nlogn)，但待排序记录的
键值几乎已排序时，情况反而恶化，每一趟快速快速排序的基
准记录位置就是第一个记录位置或最后一个记录位置。 最坏情
况下的时间复杂度为 T(n)=O(n2)。
? 快速排序的平均时间为 Tavg(n)=knlnn，其中 n为待排序序列记
录的个数,k为某个常数，经验证明，在所有同数量级的此类
（先进的）排序方法中，快速排序的常数因子 k最小。因此，
就平均时间而言，快速排序是目前被认为是最好的一种内部排
序方法。
? 快速排序递归算法需要栈空间来实现递归，一般情况下需要的空
间为 S(n)=O(log2n)，最坏情况下，需要的栈空间为 S(n)=O(n)。
? 快速排序方法是不稳定的 。
快速排序
23北京邮电大学自动化学院
? 选择排序的基本思想,每一趟在 n-i+1(i =1,2,…,n -1)个记录
中选取关键字最小的记录作为有序序列中第 i 个记录。
9.3 选择排序
? 1、简单选择排序
? 一趟简单选择排序的操作为：通过 n-1次关键字的比较，从
n- i +1个记录中选择出关键字最小的记录，并和第 i（ 1?i?
n）个记录 交换之。
? 再通过 n-2次比较，从剩余的 n-1个记录中找出关键字次小
的记录，将它与第二个记录交换
? 重复上述操作，共进行 n-1趟排序后，排序结束,
24北京邮电大学自动化学院
初始,[ 49 38 65 97 76 13 27 ]
k
j j j j j j
k k
i=1 13 49
一趟,13 [38 65 97 76 49 27 ]i=2
k k
j j j jj
27 38
二趟,13 27 [65 97 76 49 38 ]
三趟,13 27 38 [97 76 49 65 ]
四趟,13 27 38 49 [76 97 65 ]
五趟,13 27 38 49 65 [97 76 ]
六趟,13 27 38 49 65 76 [97 ]
排序结束,13 27 38 49 65 76 97
1、简单选择排序
25北京邮电大学自动化学院
? 简单选择排序过程中，所需进行记录移动的操作次数较少，
其最小值为,0”，最大值为 3(n-1)。然而，无论记录的初始
排列如何，所需进行的关键字间的比较次数相同，均为 (n(n-
1)/2。因此，总的时间复杂度也是 O（ n2）。
算法描述与算法评价 Ch8_6.c
? 从上述可见，选择排序的主要操作是进行关键字间的比较，
因此改进简单选择排序应从如何减少“比较”出发考虑。显
然，在 n个关键字中选出最小值，至少进行 n-1次比较，然
而，继续在剩余的 n-1个关键字中选择小值就并非一定要进行
n-2次比较，若能利用前 n-1次比较所得信息，则可减少以后
各趟选择排序中所用的比较次数。
26北京邮电大学自动化学院
2、树形选择排序
? 树形选择排序，又称锦标赛排序,是一种按照锦标赛
的思想进行选择排序的方法。
? 首先对 n个记录的关键字进行两两比较，然后在其中 ?n/2?
个较小者之间再进行两两比较，如此重复，直至选出最小
关键字的记录为止。
? 这个过程可用一棵有 n个叶子结点的完全二叉树表示,8个
叶子结点中依次存放排序之前的 8个关键字,每个非终端结
点中的关键字均等于其左、右孩子结点中较小的关键字，
则根结点中的关键字即为叶子结点中的最小关键字 。
27北京邮电大学自动化学院
? 在输出最小关键字之后，根据关系的可传递性，欲选出
次小关键字，仅需要将叶子结点中的最小关键字改为
“最大值”，然后从该叶子结点开始，和其左（右）兄
弟的关键字进行比较,修改从叶子结点到根的路径上各
结点的关键字，则根结点的关键字即为次小关键字 。
? 同理可依次从小到大的所有关键字。由于含有 n个叶子结
点的完全二叉树的深度为 ?log2n+1?，则在树形选择中，
除了最小关键字之外，每选择一个次小关键字仅需进行
?log2n?次比较，因此，它的时间复杂度为 O（ nlog2n)。
2、树形选择排序
28北京邮电大学自动化学院
38 6549 97 76 13 27 49
38 65 13 27
38 13
13
38 6549 97 76 ? 27 49
38 65 76 27
38 27
27
38 6549 97 76 ? ? 49
38 65 76 49
38 49
38
树形选择排序示例
输出 13之后
输出 13,27之后
29北京邮电大学自动化学院
或 (i=1,2,…..,?n/2?)ki?k2ik
i?k2i+1
ki?k2i
ki?k2i+1
3、堆排序
? 堆排序只需要一个记录大小的辅助空间，每个待排序的记录
仅占有一个存储空间。
? （ 2）堆和完全二叉树 若将和此序列对应的一维数组
（即以一维数组作此序列的存储结构）看成是一个完全二叉
树，则堆的含义表明，完全二叉树中所有非终端点的值均不
大于（或不小于）左、右孩子结点的值。由此，若序列 {k1,
k2,……k n}是堆，则堆顶元素（或完全二叉树的根）必为序
列中 n个元素的最小值（或最大值）
? （ 1）堆的定义, n个元素的序列 (k1,k2,……k n),当且仅当满
足下列关系时，称之为堆
30北京邮电大学自动化学院
例 （ 96,83,27,38,11,9）
例 （ 13,38,27,50,76,65,49,97）
96
27
91138
83
13
2738
49657650
97
? 可将堆序列看成完全二叉树，则堆顶元素
（完全二叉树的根）必为序列中 n个元素的最
小值或最大值
3、堆排序
31北京邮电大学自动化学院
? （ 3）堆排序,若在输出堆顶的最小值之后，使得剩余
n-1个元素的序列重又建成一个堆，则可得到 n个元素的
次小值；如此反复执行，便能得到一个有序序列，这个
过程称之为 堆排序 。
? 实现堆排序需解决的两个问题
? 如何由一个无序序列建成一个堆？
? 如何在输出堆顶元素之后，调整剩余元素，使之
成为一个新的堆？
? 二个问题解决方法 —— 筛选
3、堆排序
32北京邮电大学自动化学院
? （ 4）筛选
? 方法：
? 输出堆顶元素之后，以堆中最后一个元素替代之；
? 然后将根结点值与左、右子树的根结点值进行比较，并
与其中小者进行交换；
? 重复上述操作，直至叶子结点，将得到新的堆,称这个
从堆顶至叶子的调整过程为“筛选”
3、堆排序
33北京邮电大学自动化学院
例 13
2738
49657650
97
97
2738
49657650
13
输出,13
27
4938
97657650
13
输出,13
97
4938
27657650
13
输出,13 27
38
4950
27657697
13
输出,13 27
65
4950
27387697
13
输出,13 27 38
3、堆排序
34北京邮电大学自动化学院
49
6550
27387697
13
输出,13 27 38
76
6550
27384997
13
输出,13 27 38 49
50
6576
27384997
13
输出,13 27 38 49
97
6576
27384950
13
输出,13 27 38 49 50
65
9776
27384950
13
输出,13 27 38 49 50
97
6576
27384950
13
输出,13 27 38 49 50 65
3、堆排序
35北京邮电大学自动化学院
76
6597
27384950
13
输出,13 27 38 49 50 65
97
6576
27384950
13
输出,13 27 38 49 50 65 76
97
6576
27384950
13
输出,13 27 38 49 50 65 76 97
3、堆排序
36北京邮电大学自动化学院
? （ 5）建堆
? 从一个无序序列建堆的过程就是一个反复“筛选”的过
程，若将此序列看成是一个完全二叉树，则最后一个非
终端结点是 ?n/2?个元素，由此“筛选”只需从 ?n/2?个
元素开始。
? 建堆,从无序序列的第 ?n/2?个元素（即此无序序列对
应的完全二叉树的最后一个非终端结点）起，至第一个
元素止，进行反复筛选
3、堆排序
37北京邮电大学自动化学院
49
6538
27137697
50
49
6538
27137650
97
49
1338
27657650
97
49
1338
27657650
97
13
2738
49657650
97
例如 含 8个元素的无序序列
（ 49,38,65,97,76,13,27,50）
3、堆排序
38北京邮电大学自动化学院
Ch8_7.c
? 时间复杂度,最坏情况下 T(n)=O(nlogn)
? 空间复杂度,S(n)=O(1)
? 因为其运行时间主要耗费在建初始堆和调整新建堆时进行的
反复“筛选”上。对深度为 k的堆，筛选算法中进行的关键
字比较次数至多为 2(k-1)次。总共进行的比较的次数为：
<2(?log2(n-1)?+ ?log2(n-2)?+……+log 22))<2n(?log2n?)由
此,堆排序在最坏的情况下，其时间复杂度为 O(nlogn)。
? 相对于快速排序，此外，堆排序仅需一个记录大小供交换
用,…… 。因此是一种适合于排序较大文件的排序方法。
? 堆排序是一种不稳定的排序方法。
3、堆排序
39北京邮电大学自动化学院
? 归并排序 是又一类不同的排序方法。“归并”的含义是将两
个或两个以上的有序表组合成一个新的有序表
9.4 归并排序
? 排序过程,假设初始序列含有 n个记录，则可看成 n个有序
的子序列，每个子序列长度为 1，然后两两归并，得到 ?n/2?
个长度为 2或 1的有序子序列；再两两归并,…… 如此重复，
直至得到一个长度为 n的有序序列为止，这种排序方法称为
2-路归并排序。
? 2-路归并排序中的核心操作是将一维数组中前后相邻的两个
有序序列归并为一个有序序列。 —— 将两个或两个以上的
有序表组合成一个新的有序表，叫 2-路归并排序。
40北京邮电大学自动化学院
初始关键字,[49] [38] [65] [97] [76] [13] [27]
一趟归并后,[38 49] [65 97] [13 76] [27]
二趟归并后,[38 49 65 97] [13 27 76]
三趟归并后,[13 27 38 49 65 76 97]
归并排序
41北京邮电大学自动化学院
? 时间复杂度,T(n)=O(nlog2n)
Ch8_9.c
? 空间复杂度,S(n)=O(n)
? 一趟归并排序的操作是,调用 ? ?次算法将 SR[1,…,n] 中
前后相邻且长度为 h的有序序列段进行两两归并，得到前后
相邻、长度为 2h 的有序段，并存放在 TR[1,…,n] 中，整个归
并排序需进行 ?log2n?趟。可见，实现归并排序需和待排序记
录等数量的辅助空间，其时间复杂度为 O(nlog2n)。
? 与快速排序和堆排序相比，归并排序的最大特点，它是一种
稳定的排序方法 。但在一般情况下，很少利用 2路归并排序
方法进行内部排序。
h
n
2
归并排序
42北京邮电大学自动化学院
? ?2<?3<……< ?A<?2<?3<……< ?A<
? ?2<?3<……< ?A<?2<?3<……< ?A
9.5 基数排序
? 1、多关键字排序
? 每一张牌有两个“关键字”,花色和面值,且“花色”的地
位高于“面值”，在比较任意两张牌面的大小时，必须先比
较“花色”，若“花色”相同，则再比较面值。
? 已知扑克牌中 52张牌面的次序为：
? 两个关键字,花色（ ?<?<?<?）
面值（ 2<3<……<A ）
? 并且“花色”地位高于“面值”
43北京邮电大学自动化学院
? 方法 1,先对花色排序，将其分为 4个组，即梅花组、方块
组、红心组、黑心组。再对每个组分别按面值进行排序，
最后，将 4个组连接起来即可。
? 方法 2,先按 13个面值给出 13个编号组 (2号,3号,...,A
号 )，将牌按面值依次放入对应的编号组，分成 13堆。再按
花色给出 4个编号组 (梅花、方块、红心、黑心 )，将 2号组中
牌取出分别放入对应花色组，再将 3号组中牌取出分别放入
对应花色组,……,这样,4个花色组中均按面值有序，然
后，将 4个花色组依次连接起来即可。
? 由此，将扑克牌调整成如上所述次序时，通常采用的方法是：
1、多关键字排序
44北京邮电大学自动化学院
? 一般情况下，假设有 n个记录的序列 {R1,R2,…, Rn}，且每
个记录 Ri中含有 d个关键字（ Ki0,Ki1,…, Kid-1），则称序列
对关键字（ K0,K1,…, Kd-1）有序是指：对于序列中任意两
个记录 Ri和 Rj（ 1? i<j?n）都满足下列有序关系
? 为实现多关键字排序，通常有两种方法：
? 先对 最高位关键字进行排序
? 先对 最高低关键字进行排序
? （ Ki0,Ki1,…, Kid-1） <（ Kj0,Kj1,…, Kjd-1）
? 其中 K0称为 最主位关键字, Kd-1称为 最次位关键字 。
1、多关键字排序
45北京邮电大学自动化学院
? 第一种方法是先对最高位关键字 K0（ 如花色）进行排序，
将序列分成若干子序列，每个子序列中的记录都具有相同
的 K0值；
? 然后分别就每个子序列对次关键字 K1（ 如面值）进行排
序，按 K1值不同再 分成若干更小的子序列；
? 依次重复，直至对 Kd-2进行排序之后得到的每一子序列中
的记录都具有相同的关键字（ K0,K1,…, Kd-2），而后
分别每个子序列对 Kd-1进行排序，最后将所有子序列依次
联接在一起成为一个有序序列，这种方法称之为 最高优先
法（ Most Significant Digit first） （ MSD) 。
1、多关键字排序
46北京邮电大学自动化学院
? 第二种方法是从最低位关键字 Kd-1起进行排序。然后再对高
一位的关键字 Kd-2排序,…… 依次重复，直至对最高位关键
字 K0排序后，便成为一个有序序列。这种方法称之为 最低
位优先法 (LSD)。
? MSD与 LSD不同特点
? 按 MSD排序,必须将序列逐层分割成若干子序
列，然后对各子序列分别排序 。
? 按 LSD排序,不必分成子序列，对每个关键字都是
整个序列参加排序；并且可不通过关键字比较，而
通过若干次, 分配, 与, 收集, 实现排序 。
1、多关键字排序
47北京邮电大学自动化学院
2、链式基数排序
? 基数排序,借助“分配”和“收集”对单逻辑关键字进行排
序的一种方法
? 链式基数排序,用链表作存储结构的基数排序
? 逻辑关键字可以看成由若干个关键字复合而成的。例如，若
关键字是数值，且其值都在 0?k?999范围内，则可把每一个
十进制数字看成一个关键字，即可认为 K由三个关键字
（ K0,K1,K2 ）组成，其中 K0是百位数,K1是十位数，
K2是个位数；
? 又若关键字 K由五个字母组成的单词，则可看成是由五个关
键字（ （ K0,K1,K2, K3,K4 ）组成，其中 K j-1是（自
左至右）的第 j+1个字母。
48北京邮电大学自动化学院
? 由于如此分解而得的每个关键字 Kj都在相同的范围内
（对数字,0?Kj?9，对字母,A”?Kj?‘Z”），按 LSD进
行排序更为方便，只要从最小数位关键字起，按关键字
的不同值将序列中记录“分配”到 RADIX个队伍中后再
“收集”之，如此重复 d次。
? 按这种方法实现排序称之为基数排序,其中“基”指的
是 RADIX的取值范围，在上述两种关键字的情况下，它
们分别是,10”和,26”。
? 首先以静态链表存储 n个待排记录，并令表头指针指向第
一个记录，如图 (a)所示。
2、链式基数排序
49北京邮电大学自动化学院
? 第一趟分配对最低数位关键字（个位数）进行，改变记录
的指针值将链表中的记录分配至 10个链对列中去，每个队
列中的记录关键字的个位数相等，如图 (b)所示。
? 其中 f[i]和 e[i]分别为第 i个队列的头指针和尾指针；
? 第一趟收集是改变所有非空队列的对尾记录的指针值域，
令其指向下一个非空队列的对头的记录，重新将 10个队列
中的记录链成一个链表，如图（ c）所示；
? 第二趟分配，第二趟收集及第三趟分配和第三趟收集分别
是对十位数和百位数进行的，其过程和个位数相同，如图
(d)~(g)所示，至此排序完毕。
2、链式基数排序
50北京邮电大学自动化学院
例 初始状态：
278 109 063 930 589 184 505 269 008 083
109
589
269
278063930
083
184 505
008
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
一
趟
分
配
930 063 083 184 505 278 008 109 589 269
一趟收集：
2、链式基数排序
51北京邮电大学自动化学院
505 008 109 930 063 269 278 083 184 589
二趟收集：
083
184
589
063505
269
930
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
二
趟
分
配
008
109
278
930 063 083 184 505 278 008 109 589 269
一趟收集,2、链式基数排序
52北京邮电大学自动化学院
008 063 083 109 184 269 278 505 589 930
三趟收集：
109008
184
930
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
三
趟
分
配
063
083
269
278
505
589
505 008 109 930 063 269 278 083 184 589
二趟收集,2、链式基数排序
53北京邮电大学自动化学院
Ch8_10.c
? 算法评价
? 时间复杂度：分配,T(n)=O(n)
? 收集,T(n)=O(rd)
? T(n)=O(d(n+rd))
? 空间复杂度, S(n)=2rd个队列指针 。 +n个指针域空间
? 对于 n个记录（假设每个记录含有 d个关键字，每个关键字的
取值范围为 rd个值，进行链式基数排序的时间复杂度为
O(d(n+rd))，其中每一趟分配的时间复杂度为 O(n)，每一趟收
集的时间复杂度为 O(rd)，整个排序需进行 d趟分配和收集。
2、链式基数排序
? 其中：
? n—— 记录数
? d—— 关键字数
? rd—— 关键字取值范围
54北京邮电大学自动化学院
9.6 各种内部排序方法的比较讨论
排序方法 平均时间 最坏情况 辅助存储
简单排序 O(n2) O(n2) O(1)
快速排序 O(nlogn) O(n2) O(logn)
堆排序 O(nlogn) O(nlogn) O(1)
归并排序 O(nlogn) O(nlogn) O(n)
基数排序 O(n(d+rd)) O(n(d+rd)) O(rd)
55北京邮电大学自动化学院
? 从上表可以得出如下结论：
? （ 1） 从平均时间性能而言，快速排序最佳，其所需时间最
省,但快速排序在最坏情况下的时间性能不如堆排序和归
并排序。而后两者相比较的结果是，在 n较大时，归并排序
所需时间较堆排序省，但它所需的辅助存储量最多。
? （ 2）上表中的“简单排序”包括除希尔排序之外的所有插
入排序，起泡排序和简单选择排序，其中以直接插入排序
为最简单,当序列中的记录“基本有序”或 n值较小时，它
是最佳的排序方法,因此常将它和其它的排序方法，诸如
快速排序、归并排序等结合起来使用。
9.6 各种内部排序方法的比较讨论
56北京邮电大学自动化学院
? （ 3）基数排序的时间复杂度也可写成 O(nd)。因此，它
最适合用于 n值很大而关键字较小的序列。若关键字也很
大，而序列中大多数记录的“最高位关键字”均不同，则
也可先按“最高位关键字”不同将序列分成若干“小”的
子序列，而后进行直接插入排序。
? （ 4）从方法的稳定性来比较，基数排序是稳定的内排方
法，所有时间复杂度为 O(n2)的简单排序也是稳定的，然
而,快速排序、堆排序和希尔排序等时间性能较好的排序
方法都是不稳定的。
9.6 各种内部排序方法的比较讨论
57北京邮电大学自动化学院
? 一、单项选择题
? 1、排序方法中，从未排序序列中依次取出元素与已排序序
列（初始时为空）中的元素进行比较，将其放入已排序序列
的正确位置上的方法，称为
? （ A）希尔排序 （ B）冒泡排序
? （ C）插入排序 （ D）选择排序
? 2、在文件“局部有序”或文件长度较小的情况下，最佳内
排序方法是
? （ A）直接插入排序 （ B）冒泡排序
? （ C）直接选择排序 （ D）归并排序
第 9章 作业
58北京邮电大学自动化学院
? 3、对给出的一组关键字 {14,5,19,20,11,19}。若按关
键字非递减排序，第一趟排序结果为 {14,5,19,20,11，
19}，问采用的排序算法是
? （ A）简单选择排序 （ B）快速排序
? （ C）希尔排序 （ D）二路归并排序
? 4、在所有排序方法中，关键字比较的次数与记录的初始排
列次序无关的是
? （ A）希尔排序 （ B）冒泡排序
? （ C）插入排序 （ D）选择排序
第 9章 作业
59北京邮电大学自动化学院
? 二、填空题
? 1、在对一组记录 {54,38,96,23,15,72,60,45,83}
进行直接插入排序时，当把第 7个记录 60插入到有序表时，
为寻找插入位置需比较 次。
? 2、每次直接或通过基准元素间接比较两个元素，若出现逆序
排列时就交换它们的位置，此种排序方法叫做 排序；
每次使两个相邻的有序表合并成一个有序表的排序方法叫做
排序。
? 3,排序方法采用的是二分法的思想,排序方
法其数据的组织采用完全二叉树结构。
第 9章 作业
60北京邮电大学自动化学院
? 1、对于给定的键值序列 {12,2,16,30,8,28,4,10}
分别写出直接插入排序、折半插入排序、希尔排序、直接
选择排序、起泡排序的过程，并算出比较和记录移动次
数。
? 2、对于给定的键值序列 {41,62,13,84,35,96，
57,39,79,61,15,83}，分别写出快速排序、归并排
序、堆排序的各趟排序结果。
? 3、本章介绍的内部排序方法中，哪几种是稳定的？哪几
种是不稳定的？
第 9章 作业
61北京邮电大学自动化学院
第 9章 上机实习题
? 基本要求
? （ 1）选顺序存储结构存放待排序的记录。输入并存放 n个
待排序的记录
? （ 2）分别用堆排序、快速排序和归并排序方法，对待排
序记录进行排序并输出排序结果。
62北京邮电大学自动化学院
,数据结构, 考试题型
?一、填空题（ 10分）
?二、判断题（共 10分）
?三、单项选择题（共 20分，其中程序题 6分）
?四、作图题（ 6分）
?五、程序填空题 (共 18分 )
?六、简答题（ 12分）
?七、简答题 （ 12分）
?八、简答题（ 12分）
63北京邮电大学自动化学院
?一、填空题（将正确答案填在相应的空中，每题
1.5分，共 9分）
?二、判断下列陈述是否正确，正确时记为
,∨,，错误时则为,×,。（每小题 1分，共 10
分）
?1、设三角矩阵为采用压缩存储。已知 a11地址为
1,a43的存储地址是。
?1、如果某种排序算法是不稳定的，则该方法没有
实际实用价值。
,数据结构, 考试试题
64北京邮电大学自动化学院
?三、单项选择题（每小题 1.5分，共 15分，其中程
序题 6分）
?1、设有一个空栈，栈顶指针为 1000H（十六进
制，下同），现有输入序列为 1,2,3,4,5，
经过 PUSH,PUSH,POP,PUSH,POP，
PUSH,PUSH后，输出序列是,栈顶指针
是 。
?① 5,4,3,2,1 ② 2,1 ③ 2,3
④ 3,4 ⑤ 1002H ⑥ 1004H
⑦ 1005H ⑧ 1003H
,数据结构, 考试试题
65北京邮电大学自动化学院
? 简答题：对于给定的键值序列 {12,2,16,30,8,28，
4,10}分别写出直接插入排序、折半插入排序、希尔排
序、直接选择排序、起泡排序的过程，并算出比较和记录
移动次数。
第 9章 作业
