1
9.1 排序的基本概念
9.2 插入排序
9.3 选择排序
9.4 交换排序
9.5 归并排序
9.6 基数排序
9.7 性能比较
第 9章 排序
2
9.1排序的基本概念
1.排序, 将一组杂乱无章的 数据 按一定的 规律 顺次排列
起来的过程。
存放在数据表中 按关键字排序
2,排序的目的,便于查找。
3.排序算法好坏的衡量标准：
(1)时间复杂度 —— 它主要是分析记录关键字的比较次数和记
录的移动次数 。
(2)空间复杂度 —— 算法中使用的内存辅助空间的多少 。
(3)稳定性 —— 若两个记录 A和 B的关键字值相等, 但排序后 A、
B的先后次序保持不变, 则称这种排序算法是稳定的 。
4、排序的种类,分为 内部排序 和 外部排序 两大类 。
若待排序记录都在内存中，称为 内部排序 ；若待排序
记录一部分在内存，一部分在外存，则称为 外部排序 。
注,外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外
存，显然外部排序要复杂得多。
3
5.待排序记录在内存中怎样存储和处理？
① 顺序 排序 —— 排序时直接移动记录；
② 链表 排序 —— 排序时只移动指针；
③ 地址 排序 —— 排序时先移动地址，最后再移动记录。
注,地址排序 中可以增设一维数组来专门存放记录的地址。
6,内部排序的算法有哪些？
—— 按排序的规则不同，可分为 5类：
插入排序、交换排序、选择排序、归并排序、基数排序
—— 按排序算法的时间复杂度不同，可分为 3类：
? 简单的排序算法：时间效率低,O(n2)
? 先进的排序算法, 时间效率高,O( nlog2n )
? 基 数 排 序 算法：时间效率高,O( d× n)
d＝关键字的位数 (长度 )
4
9.2 插入排序
插入排序的基本思想是,每步将一个待排序的对象，按
其关键码大小,插入到前面 已经排好序的一组对象 的 适当位
置 上,直到对象全部插入为止。
简言之，边插入边排序，保证子序列中随时都是排好序的。
常用的 插入排序有,直接插入排序 和 希尔排序 两种。
一、直接插入排序
1、其基本思想是：
顺序地把待排序的数据元素按其关键字值的大小插入到已排
序数据元素子集合的适当位置。
最简单的排序法！
5
初始关键字序列,【 13】,6,3,31,9,27,5,11
第一次排序,【 6,13】,3,31,9,27,5,11
第二次排序,【 3,6,13】,31,9,27,5,11
第三次排序,【 3,6,13,31】,9,27,5,11
第四次排序,【 3,6,9,13,31】,27,5,11
第五次排序,【 3,6,9,13,27,31】,5,11
第六次排序,【 3,5,6,9,13,27,31】,11
第七次排序,【 3,5,6,9,11,13,27,31】
例 1,关键字序列 T=（ 13,6,3,31,9,27,5,11），
请写出直接插入排序的中间过程序列。
注,方括号 [ ]中为已排序记录的关键字，下划横线的 关键字
表示它对应的记录后移一个位置。
6
2,C语言程序
void InsertSort(DataType a[],int n)
/*用直接插入法对 a[0]--a[n-1]排序 */
{ int i,j; DataType temp;
for(i = 0; i < n-1; i++) {
temp = a[i+1];
j = i;
while(j > -1 && temp.key < a[j].key) {
a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}
}
7
void main(void)
{ DataType test[6]={64,5,7,89,6,24};
int i,n = 6; SeqList myList;
ListInitiate(&myList);
for(i = 0; i < n; i++)
ListInsert(&myList,i,test[i]);
InsertSort(myList.list,myList.size);
for(i=0; i<n; i++)
printf("%d ",myList.list[i].key);
}
#include <stdio.h>
typedef int KeyType;
typedef struct
{KeyType key;
} DataType;
#define MaxSize 100
#include "SeqList.h"
8
(1)时间效率,因为在最坏情况下，所有元素的比较次数总
和为（ 0＋ 1＋ … ＋ n-1)→O(n 2)。其他情况下也要
考虑移动元素的次数。 故时间复杂度为 O(n2)
(2)空间效率,仅占用 1个缓冲单元 —— O（ 1）
(3)算法的稳定性,稳定
3、直接插入排序算法分析
二、希尔（ shell）排序 （又称缩小增量排序）
1、基本思想, 把整个待排序的数据元素分成若干个小组，对同
一小组内的数据元素用直接插入法排序；小组的个数逐次缩小，
当完成了所有数据元素都在一个组内的排序后排序过程结束。
2,技巧,小组的构成不是简单地, 逐段分割,,而是将相隔某
个增量 dk的记录组成一个小组,让增量 dk逐趟缩短（例如依次取
5,3,1），直到 dk＝ 1为止。
3、优点,让关键字值小的元素能很快前移，且序列若基本有序
时，再用直接插入排序处理，时间效率会高很多。
9
例 2,设待排序的序列中有 12个记录，它们的关键字序列 T=(65，
34,25,87,12,38,56,46,14,77,92,23），请写出
希尔排序的具体实现过程。
算法分析,开始时 d 的值较大，子序列中的对象较少，排序速度
较快；随着排序进展,d值逐渐变小，子序列中对象个数
逐渐变多，由于前面工作的基础，大多数记录已基本有序，
所以排序速度仍然很快。
通常,di+1=di/2 (结果取整）
时间效率,O(n(log2n)2)
空间效率,O（ 1） —— 因为仅占用 1个缓冲单元
算法的稳定性,不稳定
下面给出 希尔排序的具体实现过程：
10
65 34 25 87 12 38 56 46 14 77 92 23
56 34 14 77 12 23 65 46 25 87 92 38结果序列
56 34 14 77 12 23 65 46 25 87 92 38
56 12 14 65 34 23 77 46 25 87 92 38结果序列
56 12 14 65 34 23 77 46 25 87 92 38
12 14 23 25 34 38 46 56 65 77 87 92结果序列
(a)
(b)
(c)
第 1趟 (d=6)
第 2趟 (d=3)
第 3趟 (d=1)
11
4,C语言程序
void ShellSort(DataType a[],int n,int d[],int numOfD)
{ int i,j,k,m,span;
DataType temp;
for(m = 0; m < numOfD; m++) {
span = d[m];
for(k = 0; k < span; k++) {
for(i = k; i < n-span; i = i+span) {
temp = a[i+span]; j = i;
while(j > -1 && temp.key <= a[j].key) {
a[j+span] = a[j]; j = j-span; }
a[j+span] = temp; }
}
} }
12
练习：
1,欲将序列（ Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码
按字母升序重排，则初始步长为 4的希尔排序一趟的结果是？
答,原始序列,Q,H,C,Y,P,A,M,S,R,D,F,X
shell一趟后,P,Q,R,A,D,H,C,F,M,S,X,Y
2,以关键字序列 （ 256,301,751,129,937,863,742，
694,076,438） 为例, 写出执行希尔排序 （ 取 d=5,3,1） 算
法的 各趟 排序结束时, 关键字序列的状态 。
解,原始序列, 256,301,751,129,937,863,742,694,076,438
第 1趟
d=5
第 2趟
d=3
第 3趟
d=1
256,301,694,076,438,863,742,751,129,937
076,301,129,256,438,694,742,751,863,937
076,129,256,301,438,694,742,751,863,937
13
9.3 选择排序
选择排序 的基本思想是,每次 从待排序的数据元
素集合中 选取 关键字 最小（或最大） 的数据元素 放到
数据元素集合的 最前（或最后）,数据元素集合不断
缩小，当数据元素集合为空时选择排序结束。
常用的选择排序算法：
（ 1） 直接选择排序
（ 2） 堆排序
14
一、直接选择排序
1,其基本思想
每经过一趟比较就找出一个最小值, 与待排序列
最前面的位置互换即可 。
（ 即 从待排序的数据元素集合中 选取关键字最小 的数
据元素并将它与原始数据元素集合中的 第一个 数据元
素 交换位置 ；然后从 不 包括 第一个位置 的数据元素集
合中 选取关键字最小 的数据元素并将它与原始数据集
合中的 第二个 数据元素交换位置；如此重复, 直到数
据元素集合中只剩一个数据元素为止 。 ）
2,优缺点
优点,实现简单
缺点,每趟只能确定一个元素, 表长为 n时需要 n-1趟
15
例 3,关键字序列 T= （ 21,25,49,25*,16,08），
请给出简单选择排序的具体实现过程。
原始序列,21,25,49,25*,16,08
第 1趟
第 2趟
第 3趟
第 4趟
第 5趟
08,25,49,25*,16,21
08,16,49,25*,25,21
08,16,21,25*,25,49
08,16,21,25*,25,49
08,16,21,25*,25,49
3、算法分析
时间效率,O(n2)—— 虽移动次数较少，但比较次数仍多。
空间效率,O（ 1） —— 没有附加单元（仅用到 1个 temp)
算法的稳定性,不稳定
16
4,c语言程序
void SelectSort(DataType a[],int n)
{ int i,j,small; DataType temp;
for(i = 0; i < n-1; i++)
{ small = i;
for(j = i+1;j<n;j++)
if(a[j].key < a[small].key) small=j;
if(small != i){ temp = a[i];
a[i] = a[small];
a[small] = temp;
}
}
}
17
二、堆排序
1,什么是堆？
堆的定义,设有 n个数据元素的序列 k0,k1,…, kn-1，当且
仅当满足下述关系之一时，称之为堆。
ki ≤ k2i+1
ki ≤ k2i+2
ki ≥k2i+1
ki ≥ k2i+2或者
i=0,2,… (n -1)/2
2,怎样建堆？ 3,怎样堆排序？
解释,如果让满足以上条件的元素序列 （ k０, k１, …, kn－１ ）
顺次排成一棵 完全二叉树,则此树的特点是：
树中所有结点的值均大于（或小于）其左右孩子，此树的根
结点（ 即堆顶） 必最大（或最小）。
18
例 4：有序列 T1=（ 08,25,49,46,58,67）和序列 T2=
（ 91,85,76,66,58,67,55）,判断它们是否,堆”？
08
25
46
49
58 67
2 3
4 5 6
1
（大根堆）
91
85
66
76
58 67
2 3
4 5 6
1
55
7
√ （小根堆） √
（小顶堆）
（最小堆）
（大顶堆）
（最大堆）
19
终端结点（即叶子）没有任何子女，无需单独调整
步骤,从最后一个 非终端结点 开始往前逐步调整，让每个双
亲大于（或小于）子女，直到根结点为止。
21
25
25*
49
16 08
1
2 3
4 5 6
例,关键字序列 T= (21,25,49,25*,16,08），请建 大根堆 。
2,怎样建堆？
解,为便于理解，先将原始序列画成完全二叉树的形式：
这样可以很清晰地从 ?(n-1)/2?开始调整。
完全二叉树的第一个非终端结点
编号必为 ?n/2? ！！ (性质 5)
21 i=3:
49
而且 21还应当向下比较！！
49大于 08，不必调整；
i=2,25大于 25*和 16，也不必调整；
i=1,21小于 25和 49，要调整！
20
3,怎样进行整个序列的堆排序？
*难点,将堆的当前顶点输出后，如何将剩余序列重新
调整为堆？
*方法,将当前顶点 与堆尾记录交换,然后 仿建堆动作
重新调整，如此反复直至排序结束 。
*基于初始堆进行堆排序的算法步骤：
堆的第一个对象 r[0]具有最大的关键码，将 r[0]
与 r[n]对调，把具有最大关键码的对象交换到最后 ;
再对前面的 n-1个对象，使用堆的调整算法，重新
建立堆。结果具有次最大关键码的对象又上浮到堆顶，
即 r[0]位置 ;
再对调 r[0]和 r[n-1]，然后对前 n-2个对象重新调
整,… 如此反复，最后得到全部排序好的对象序列。
21
例 5,对刚才建好的大根堆进行排序：
08 25 21 25* 16 49
交换 1号与 6 号记录
r[0] r[n]
49
25
25*
21
16 08
1
2 3
4 5 6
49 25 21 25* 16 08
初始最大堆
25
25* 16
21
1
3
654
2
08
49
22
16 25* 21 08 25 49
交换 1号与 5 号记录
08 25 21 25* 16 49
从 1 号到 5 号 重新
调整为最大堆
08
25
25*
21
16 49
1
2 3
4 5 6
16
25*
08 25
21
49
1
3
654
2
08
25
25*
08
25 25* 21 08 16
23
08 16 21 25* 25 49
交换 1 号与 4 号记录
25* 16 21 08 25 49
从 1号到 4号 重新
调整为最大堆
25*
16
08
21
25 49
1
2 3
4 5 6
08
16
25* 25
21
49
1
3
654
2
16
25*
24
08 16 21 25* 25 49
交换 1号与 3 号记录
21 16 08 25* 25 49
从 1 号到 3号 重新
调整为最大堆
2116
25*
08
25 49
1
2 3
4 5 6
08
16
25* 25
21
49
1
3
654
2
21
08
25
08 16 21 25* 25 49
交换 1 号与 2 号记录
排序完毕。
16 08 21 25* 25 49
从 1 号到 2 号 重新
调整为最大堆
16
08
25*
21
25 49
1
2 3
4 5 6
08
16
25* 25
21
49
1
3
654
2
16
08
26
4,堆排序算法分析：
? 时间效率,O(nlog2n)。 因为整个排序过程中需
要调用 n-1次堆顶点的调整，而每次堆排序算法
本身耗时为 log2n；
? 空间效率,O(1)。 仅在第二个 for循环中交换记
录时用到一个临时变量 temp。
? 稳定性,不稳定。
? 优点,对小文件效果不明显，但对大文件有效。
27
9.4 交换排序
交换排序的基本思想是：利用交换数据元素
的位置进行排序的方法。
交换排序的主要算法有：
1) 冒泡排序
2) 快速排序
28
一、冒泡排序
1、基本思路,每趟不断将记录两两比较，并按, 前小后大,
（或, 前大后小, ）规则交换。
2、优点,每趟结束时，不仅能挤出一个最大值到最后面位
置，还能 同时部分理顺其他元素 ；一旦下趟没有交
换发生，还可以 提前结束排序 。
例 6,关键字序列 T=(21,25,49,25*,16,08），请按从
小到大的顺序，写出冒泡排序的具体实现过程。
初态：
第 1趟
第 2趟
第 3趟
第 4趟
第 5趟
21,25,49,25*,16,08
21,25,25*,16,08, 49
21,25,16,08, 25*,49
21,16,08, 25,25*,49
16,08, 21,25,25*,49
08,16,21,25,25*,49
29
3,C语言实现
void BubbleSort(DataType a[],int n)
{ int i,j,flag = 1;
DataType temp;
for(i = 1; i < n && flag == 1; i++)
{ flag = 0;
for(j = 0; j < n-i; j++)
{ if(a[j].key > a[j+1].key){
flag = 1;
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp; }
}
}
}
30
4、冒泡排序的算法分析
?最好情况,初始排列已经有序，只执行一趟起泡，做 n-1
次关键码比较，不移动对象。
?最坏情形,初始排列逆序,算法要执行 n-1趟起泡，第 i趟
(1? i? n) 做了 n- i 次关键码比较，执行了 n-i 次对象交换。
此时的比较总次数 KCN和记录移动次数 RMN为：
?
?
?
?
?
?
????
????
1
1
1
1
1
2
3
3
1
2
1
n
i
n
i
nninR M N
nninK C N
)()(
)()(
因此：
时间效率,O（ n2) — 因为要考虑最坏情况
空间效率,O（ 1） — 只在交换时用到一个缓冲单元
稳 定 性,稳定 — 25和 25*在排序前后的次序未改变
31
二、快速排序
1、基本思想,从待排序列中任取一个元素 (例如取第一个 ) 作
为中心，所有比它小的元素一律前放，所有比它大的元素一律
后放，形成左右两个子表；然后再对各子表重新选择中心元素
并依此规则调整，直到每个子表的元素只剩一个。此时便为有
序序列了。
2、优点,因为每趟可以确定不止一个元素的位置，而且呈指数
增加，所以特别快。
例 7,关键字序列 T=(60,55,48,37,10,90,84,36），请
按从小到大的顺序，写出快速排序的具体实现过程。
初始关键字序列:
(1)
(2)
{ 60 55 48 37 10 90 84 36
{ 36 55 48 37 10} 60 { 84 90}
{ 10 } 36 { 48 37 55} 60 84 { 90 }
(3) { 10 } 36 { 37 } 48 { 55 } 60 84 90
最后结果 10 36 37 48 55 60 84 90
32
60 55 48 37 10 90 84 36
36 55 48 37 10 90 84
90
90
36 55 48 37 10 90 84
36 55 48 37 10 90 84
36 55 48 37 10 90 84
36 55 48 37 10 90 84
36 55 48 37 10 90 84
36 55 48 37 10 84
36 55 48 37 10 60 84
i
i
i
i
i
i
i
i
j
j
j
j
j
j
j
j
i j
初始关键字序列:
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
第一次快速排序过程
33
3,C语言实现
void QuickSort(DataType a[],int low,int high)
{ int i = low,j = high;
DataType temp = a[low];
while(i < j)
{ while(i < j && temp.key <= a[j].key) j--;
if(i < j) { a[i] = a[j]; i++; }
while(i < j && a[i].key < temp.key) i++;
if(i < j) { a[j] = a[i]; j--; }
}
a[i] = temp;
if(low < i) QuickSort(a,low,i-1);
if(i < high) QuickSort(a,j+1,high);
}
34
时间效率,O(nlog2n) — 因为每趟确定的元素呈指数增加
空间效率,O（ log2n） — 因为递归要用栈 (存每层 low,high
和 pivot)
稳 定 性,不 稳 定 — 因为有跳跃式交换。
4、快速排序算法分析：
9.1 排序的基本概念
9.2 插入排序
9.3 选择排序
9.4 交换排序
9.5 归并排序
9.6 基数排序
9.7 性能比较
第 9章 排序
2
9.1排序的基本概念
1.排序, 将一组杂乱无章的 数据 按一定的 规律 顺次排列
起来的过程。
存放在数据表中 按关键字排序
2,排序的目的,便于查找。
3.排序算法好坏的衡量标准：
(1)时间复杂度 —— 它主要是分析记录关键字的比较次数和记
录的移动次数 。
(2)空间复杂度 —— 算法中使用的内存辅助空间的多少 。
(3)稳定性 —— 若两个记录 A和 B的关键字值相等, 但排序后 A、
B的先后次序保持不变, 则称这种排序算法是稳定的 。
4、排序的种类,分为 内部排序 和 外部排序 两大类 。
若待排序记录都在内存中，称为 内部排序 ；若待排序
记录一部分在内存，一部分在外存，则称为 外部排序 。
注,外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外
存，显然外部排序要复杂得多。
3
5.待排序记录在内存中怎样存储和处理？
① 顺序 排序 —— 排序时直接移动记录；
② 链表 排序 —— 排序时只移动指针；
③ 地址 排序 —— 排序时先移动地址，最后再移动记录。
注,地址排序 中可以增设一维数组来专门存放记录的地址。
6,内部排序的算法有哪些？
—— 按排序的规则不同，可分为 5类：
插入排序、交换排序、选择排序、归并排序、基数排序
—— 按排序算法的时间复杂度不同，可分为 3类：
? 简单的排序算法：时间效率低,O(n2)
? 先进的排序算法, 时间效率高,O( nlog2n )
? 基 数 排 序 算法：时间效率高,O( d× n)
d＝关键字的位数 (长度 )
4
9.2 插入排序
插入排序的基本思想是,每步将一个待排序的对象，按
其关键码大小,插入到前面 已经排好序的一组对象 的 适当位
置 上,直到对象全部插入为止。
简言之，边插入边排序，保证子序列中随时都是排好序的。
常用的 插入排序有,直接插入排序 和 希尔排序 两种。
一、直接插入排序
1、其基本思想是：
顺序地把待排序的数据元素按其关键字值的大小插入到已排
序数据元素子集合的适当位置。
最简单的排序法！
5
初始关键字序列,【 13】,6,3,31,9,27,5,11
第一次排序,【 6,13】,3,31,9,27,5,11
第二次排序,【 3,6,13】,31,9,27,5,11
第三次排序,【 3,6,13,31】,9,27,5,11
第四次排序,【 3,6,9,13,31】,27,5,11
第五次排序,【 3,6,9,13,27,31】,5,11
第六次排序,【 3,5,6,9,13,27,31】,11
第七次排序,【 3,5,6,9,11,13,27,31】
例 1,关键字序列 T=（ 13,6,3,31,9,27,5,11），
请写出直接插入排序的中间过程序列。
注,方括号 [ ]中为已排序记录的关键字，下划横线的 关键字
表示它对应的记录后移一个位置。
6
2,C语言程序
void InsertSort(DataType a[],int n)
/*用直接插入法对 a[0]--a[n-1]排序 */
{ int i,j; DataType temp;
for(i = 0; i < n-1; i++) {
temp = a[i+1];
j = i;
while(j > -1 && temp.key < a[j].key) {
a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}
}
7
void main(void)
{ DataType test[6]={64,5,7,89,6,24};
int i,n = 6; SeqList myList;
ListInitiate(&myList);
for(i = 0; i < n; i++)
ListInsert(&myList,i,test[i]);
InsertSort(myList.list,myList.size);
for(i=0; i<n; i++)
printf("%d ",myList.list[i].key);
}
#include <stdio.h>
typedef int KeyType;
typedef struct
{KeyType key;
} DataType;
#define MaxSize 100
#include "SeqList.h"
8
(1)时间效率,因为在最坏情况下，所有元素的比较次数总
和为（ 0＋ 1＋ … ＋ n-1)→O(n 2)。其他情况下也要
考虑移动元素的次数。 故时间复杂度为 O(n2)
(2)空间效率,仅占用 1个缓冲单元 —— O（ 1）
(3)算法的稳定性,稳定
3、直接插入排序算法分析
二、希尔（ shell）排序 （又称缩小增量排序）
1、基本思想, 把整个待排序的数据元素分成若干个小组，对同
一小组内的数据元素用直接插入法排序；小组的个数逐次缩小，
当完成了所有数据元素都在一个组内的排序后排序过程结束。
2,技巧,小组的构成不是简单地, 逐段分割,,而是将相隔某
个增量 dk的记录组成一个小组,让增量 dk逐趟缩短（例如依次取
5,3,1），直到 dk＝ 1为止。
3、优点,让关键字值小的元素能很快前移，且序列若基本有序
时，再用直接插入排序处理，时间效率会高很多。
9
例 2,设待排序的序列中有 12个记录，它们的关键字序列 T=(65，
34,25,87,12,38,56,46,14,77,92,23），请写出
希尔排序的具体实现过程。
算法分析,开始时 d 的值较大，子序列中的对象较少，排序速度
较快；随着排序进展,d值逐渐变小，子序列中对象个数
逐渐变多，由于前面工作的基础，大多数记录已基本有序，
所以排序速度仍然很快。
通常,di+1=di/2 (结果取整）
时间效率,O(n(log2n)2)
空间效率,O（ 1） —— 因为仅占用 1个缓冲单元
算法的稳定性,不稳定
下面给出 希尔排序的具体实现过程：
10
65 34 25 87 12 38 56 46 14 77 92 23
56 34 14 77 12 23 65 46 25 87 92 38结果序列
56 34 14 77 12 23 65 46 25 87 92 38
56 12 14 65 34 23 77 46 25 87 92 38结果序列
56 12 14 65 34 23 77 46 25 87 92 38
12 14 23 25 34 38 46 56 65 77 87 92结果序列
(a)
(b)
(c)
第 1趟 (d=6)
第 2趟 (d=3)
第 3趟 (d=1)
11
4,C语言程序
void ShellSort(DataType a[],int n,int d[],int numOfD)
{ int i,j,k,m,span;
DataType temp;
for(m = 0; m < numOfD; m++) {
span = d[m];
for(k = 0; k < span; k++) {
for(i = k; i < n-span; i = i+span) {
temp = a[i+span]; j = i;
while(j > -1 && temp.key <= a[j].key) {
a[j+span] = a[j]; j = j-span; }
a[j+span] = temp; }
}
} }
12
练习：
1,欲将序列（ Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码
按字母升序重排，则初始步长为 4的希尔排序一趟的结果是？
答,原始序列,Q,H,C,Y,P,A,M,S,R,D,F,X
shell一趟后,P,Q,R,A,D,H,C,F,M,S,X,Y
2,以关键字序列 （ 256,301,751,129,937,863,742，
694,076,438） 为例, 写出执行希尔排序 （ 取 d=5,3,1） 算
法的 各趟 排序结束时, 关键字序列的状态 。
解,原始序列, 256,301,751,129,937,863,742,694,076,438
第 1趟
d=5
第 2趟
d=3
第 3趟
d=1
256,301,694,076,438,863,742,751,129,937
076,301,129,256,438,694,742,751,863,937
076,129,256,301,438,694,742,751,863,937
13
9.3 选择排序
选择排序 的基本思想是,每次 从待排序的数据元
素集合中 选取 关键字 最小（或最大） 的数据元素 放到
数据元素集合的 最前（或最后）,数据元素集合不断
缩小，当数据元素集合为空时选择排序结束。
常用的选择排序算法：
（ 1） 直接选择排序
（ 2） 堆排序
14
一、直接选择排序
1,其基本思想
每经过一趟比较就找出一个最小值, 与待排序列
最前面的位置互换即可 。
（ 即 从待排序的数据元素集合中 选取关键字最小 的数
据元素并将它与原始数据元素集合中的 第一个 数据元
素 交换位置 ；然后从 不 包括 第一个位置 的数据元素集
合中 选取关键字最小 的数据元素并将它与原始数据集
合中的 第二个 数据元素交换位置；如此重复, 直到数
据元素集合中只剩一个数据元素为止 。 ）
2,优缺点
优点,实现简单
缺点,每趟只能确定一个元素, 表长为 n时需要 n-1趟
15
例 3,关键字序列 T= （ 21,25,49,25*,16,08），
请给出简单选择排序的具体实现过程。
原始序列,21,25,49,25*,16,08
第 1趟
第 2趟
第 3趟
第 4趟
第 5趟
08,25,49,25*,16,21
08,16,49,25*,25,21
08,16,21,25*,25,49
08,16,21,25*,25,49
08,16,21,25*,25,49
3、算法分析
时间效率,O(n2)—— 虽移动次数较少，但比较次数仍多。
空间效率,O（ 1） —— 没有附加单元（仅用到 1个 temp)
算法的稳定性,不稳定
16
4,c语言程序
void SelectSort(DataType a[],int n)
{ int i,j,small; DataType temp;
for(i = 0; i < n-1; i++)
{ small = i;
for(j = i+1;j<n;j++)
if(a[j].key < a[small].key) small=j;
if(small != i){ temp = a[i];
a[i] = a[small];
a[small] = temp;
}
}
}
17
二、堆排序
1,什么是堆？
堆的定义,设有 n个数据元素的序列 k0,k1,…, kn-1，当且
仅当满足下述关系之一时，称之为堆。
ki ≤ k2i+1
ki ≤ k2i+2
ki ≥k2i+1
ki ≥ k2i+2或者
i=0,2,… (n -1)/2
2,怎样建堆？ 3,怎样堆排序？
解释,如果让满足以上条件的元素序列 （ k０, k１, …, kn－１ ）
顺次排成一棵 完全二叉树,则此树的特点是：
树中所有结点的值均大于（或小于）其左右孩子，此树的根
结点（ 即堆顶） 必最大（或最小）。
18
例 4：有序列 T1=（ 08,25,49,46,58,67）和序列 T2=
（ 91,85,76,66,58,67,55）,判断它们是否,堆”？
08
25
46
49
58 67
2 3
4 5 6
1
（大根堆）
91
85
66
76
58 67
2 3
4 5 6
1
55
7
√ （小根堆） √
（小顶堆）
（最小堆）
（大顶堆）
（最大堆）
19
终端结点（即叶子）没有任何子女，无需单独调整
步骤,从最后一个 非终端结点 开始往前逐步调整，让每个双
亲大于（或小于）子女，直到根结点为止。
21
25
25*
49
16 08
1
2 3
4 5 6
例,关键字序列 T= (21,25,49,25*,16,08），请建 大根堆 。
2,怎样建堆？
解,为便于理解，先将原始序列画成完全二叉树的形式：
这样可以很清晰地从 ?(n-1)/2?开始调整。
完全二叉树的第一个非终端结点
编号必为 ?n/2? ！！ (性质 5)
21 i=3:
49
而且 21还应当向下比较！！
49大于 08，不必调整；
i=2,25大于 25*和 16，也不必调整；
i=1,21小于 25和 49，要调整！
20
3,怎样进行整个序列的堆排序？
*难点,将堆的当前顶点输出后，如何将剩余序列重新
调整为堆？
*方法,将当前顶点 与堆尾记录交换,然后 仿建堆动作
重新调整，如此反复直至排序结束 。
*基于初始堆进行堆排序的算法步骤：
堆的第一个对象 r[0]具有最大的关键码，将 r[0]
与 r[n]对调，把具有最大关键码的对象交换到最后 ;
再对前面的 n-1个对象，使用堆的调整算法，重新
建立堆。结果具有次最大关键码的对象又上浮到堆顶，
即 r[0]位置 ;
再对调 r[0]和 r[n-1]，然后对前 n-2个对象重新调
整,… 如此反复，最后得到全部排序好的对象序列。
21
例 5,对刚才建好的大根堆进行排序：
08 25 21 25* 16 49
交换 1号与 6 号记录
r[0] r[n]
49
25
25*
21
16 08
1
2 3
4 5 6
49 25 21 25* 16 08
初始最大堆
25
25* 16
21
1
3
654
2
08
49
22
16 25* 21 08 25 49
交换 1号与 5 号记录
08 25 21 25* 16 49
从 1 号到 5 号 重新
调整为最大堆
08
25
25*
21
16 49
1
2 3
4 5 6
16
25*
08 25
21
49
1
3
654
2
08
25
25*
08
25 25* 21 08 16
23
08 16 21 25* 25 49
交换 1 号与 4 号记录
25* 16 21 08 25 49
从 1号到 4号 重新
调整为最大堆
25*
16
08
21
25 49
1
2 3
4 5 6
08
16
25* 25
21
49
1
3
654
2
16
25*
24
08 16 21 25* 25 49
交换 1号与 3 号记录
21 16 08 25* 25 49
从 1 号到 3号 重新
调整为最大堆
2116
25*
08
25 49
1
2 3
4 5 6
08
16
25* 25
21
49
1
3
654
2
21
08
25
08 16 21 25* 25 49
交换 1 号与 2 号记录
排序完毕。
16 08 21 25* 25 49
从 1 号到 2 号 重新
调整为最大堆
16
08
25*
21
25 49
1
2 3
4 5 6
08
16
25* 25
21
49
1
3
654
2
16
08
26
4,堆排序算法分析：
? 时间效率,O(nlog2n)。 因为整个排序过程中需
要调用 n-1次堆顶点的调整，而每次堆排序算法
本身耗时为 log2n；
? 空间效率,O(1)。 仅在第二个 for循环中交换记
录时用到一个临时变量 temp。
? 稳定性,不稳定。
? 优点,对小文件效果不明显，但对大文件有效。
27
9.4 交换排序
交换排序的基本思想是：利用交换数据元素
的位置进行排序的方法。
交换排序的主要算法有：
1) 冒泡排序
2) 快速排序
28
一、冒泡排序
1、基本思路,每趟不断将记录两两比较，并按, 前小后大,
（或, 前大后小, ）规则交换。
2、优点,每趟结束时，不仅能挤出一个最大值到最后面位
置，还能 同时部分理顺其他元素 ；一旦下趟没有交
换发生，还可以 提前结束排序 。
例 6,关键字序列 T=(21,25,49,25*,16,08），请按从
小到大的顺序，写出冒泡排序的具体实现过程。
初态：
第 1趟
第 2趟
第 3趟
第 4趟
第 5趟
21,25,49,25*,16,08
21,25,25*,16,08, 49
21,25,16,08, 25*,49
21,16,08, 25,25*,49
16,08, 21,25,25*,49
08,16,21,25,25*,49
29
3,C语言实现
void BubbleSort(DataType a[],int n)
{ int i,j,flag = 1;
DataType temp;
for(i = 1; i < n && flag == 1; i++)
{ flag = 0;
for(j = 0; j < n-i; j++)
{ if(a[j].key > a[j+1].key){
flag = 1;
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp; }
}
}
}
30
4、冒泡排序的算法分析
?最好情况,初始排列已经有序，只执行一趟起泡，做 n-1
次关键码比较，不移动对象。
?最坏情形,初始排列逆序,算法要执行 n-1趟起泡，第 i趟
(1? i? n) 做了 n- i 次关键码比较，执行了 n-i 次对象交换。
此时的比较总次数 KCN和记录移动次数 RMN为：
?
?
?
?
?
?
????
????
1
1
1
1
1
2
3
3
1
2
1
n
i
n
i
nninR M N
nninK C N
)()(
)()(
因此：
时间效率,O（ n2) — 因为要考虑最坏情况
空间效率,O（ 1） — 只在交换时用到一个缓冲单元
稳 定 性,稳定 — 25和 25*在排序前后的次序未改变
31
二、快速排序
1、基本思想,从待排序列中任取一个元素 (例如取第一个 ) 作
为中心，所有比它小的元素一律前放，所有比它大的元素一律
后放，形成左右两个子表；然后再对各子表重新选择中心元素
并依此规则调整，直到每个子表的元素只剩一个。此时便为有
序序列了。
2、优点,因为每趟可以确定不止一个元素的位置，而且呈指数
增加，所以特别快。
例 7,关键字序列 T=(60,55,48,37,10,90,84,36），请
按从小到大的顺序，写出快速排序的具体实现过程。
初始关键字序列:
(1)
(2)
{ 60 55 48 37 10 90 84 36
{ 36 55 48 37 10} 60 { 84 90}
{ 10 } 36 { 48 37 55} 60 84 { 90 }
(3) { 10 } 36 { 37 } 48 { 55 } 60 84 90
最后结果 10 36 37 48 55 60 84 90
32
60 55 48 37 10 90 84 36
36 55 48 37 10 90 84
90
90
36 55 48 37 10 90 84
36 55 48 37 10 90 84
36 55 48 37 10 90 84
36 55 48 37 10 90 84
36 55 48 37 10 90 84
36 55 48 37 10 84
36 55 48 37 10 60 84
i
i
i
i
i
i
i
i
j
j
j
j
j
j
j
j
i j
初始关键字序列:
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
第一次快速排序过程
33
3,C语言实现
void QuickSort(DataType a[],int low,int high)
{ int i = low,j = high;
DataType temp = a[low];
while(i < j)
{ while(i < j && temp.key <= a[j].key) j--;
if(i < j) { a[i] = a[j]; i++; }
while(i < j && a[i].key < temp.key) i++;
if(i < j) { a[j] = a[i]; j--; }
}
a[i] = temp;
if(low < i) QuickSort(a,low,i-1);
if(i < high) QuickSort(a,j+1,high);
}
34
时间效率,O(nlog2n) — 因为每趟确定的元素呈指数增加
空间效率,O（ log2n） — 因为递归要用栈 (存每层 low,high
和 pivot)
稳 定 性,不 稳 定 — 因为有跳跃式交换。
4、快速排序算法分析：
