1
第 10 章 排序算法
2
§ 10.1 概述
? 排序的主要目的是便于以后在已排序的集合中查找检
索某一成员
? 若干概念
– 关键字
– 排序
– 排序的稳定性
– 内排序
– 外排序
– 多键排序
3
§ 10.1 概述
? 排序方法进行分类
– 插入排序
– 交换排序
– 选择排序
– 归并排序
– 分配排序
4
§ 10.1 概述
? 算法的时间复杂性
– 通常只考虑键值的比较次数和记录的移动次数
? 评价排序的另一个主要标准是执行算法所需的附加空
间
5
§ 10.2 插入排序
? 插入排序的基本方法是：每步将一个待排序的记录按
其关键字的大小插到前面已经排序的序列中的适当位
置，直到全部记录插入完毕为止。
6
§ 10.2.1 直接插入排序
初始键值序列
[46] 58 15 45 90 18 10 62
i=2 [46 58] 15 45 90 18 10 62
i=3 [15 46 58] 45 90 18 10 62
i=4 [15 45 46 58] 90 18 10 62
i=5 [15 45 46 58 90] 18 10 62
i=6 [15 18 45 46 58 90] 10 62
i=7 [10 15 18 45 46 58 90] 62
i=8 [10 15 18 45 46 58 62 90]
图 10-1直接插入排序过程示例
7
§ 10.2.1 直接插入排序
?可以将插入排序粗略地描述为：
SortInsertion(int a[],long n)
{
for (i=1; i<n; i++)
将 a[i]插入到 a[0]—a[i-1]中, 并使其保持有序
}
8
插入排序的程序：
int SortInsertion(int a[],long n)
{
int x,i,,j;
for (i=1; i<n; i++)
{
x=a[i];
j=i-1;
while (j>=0 && x<a[j])
{
a[j+1] = a[j];
j--;
}
a[j+1] = x;
} //for
return 0;
}
9
§ 10.2.2 其他插入排序算法
?除了直接插入排序外, 还有其他形式的插入排序, 如折半插入
排序, 表插入排序和希尔排序等 。
?它们是对直接插入排序的改进 。 改进的关键点是, 如何尽快地
找到插入位置 。
10
§ 10.3 交换排序
?所谓交换, 就是根据记录集中两个记录键值的比较结果来对换
这两个记录在序列中的位置
?交换排序的特点是：将键值较大的记录向记录集的一端移动,
键值较小的记录向另一端移动 。
11
§ 10.3.1 冒泡排序
? 设初始记录集为
20 30 10 45 33 22 55 50
? 则第一趟冒泡的过程为：
20 30 10 45 33 22 55 50 //20与 30比较, 未交换
20 10 30 45 33 22 55 50 //30与 10比较, 交换
20 10 30 45 33 22 55 50 //30与 45比较, 未交换
20 10 30 33 45 22 55 50 //45与 33比较, 交换
20 10 30 33 22 45 55 50 //45与 22比较, 交换
20 10 30 33 22 45 55 50 //45与 55比较, 未交换
20 10 30 33 22 45 50 55 //55与 50比较, 交换
12
§ 10.3.1 冒泡排序
?每趟的结果
10 20 30 22 33 45 50 55 //第 2趟
10 20 22 30 33 45 50 55 //第 3趟
10 20 22 30 33 45 50 55 //第 4趟
10 20 22 30 33 45 50 55 //第 5趟
10 20 22 30 33 45 50 55 //第 6趟
10 20 22 30 33 45 50 55 //第 7趟
10 20 22 30 33 45 50 55 //第 8趟
13
§ 10.3.3 快速排序
(一 )基本思想
?基本思想是：在待排序的 n个记录中任取一个记录（例如就
取第一个记录），以该记录的键值为标准，将所有记录分为
两组（一般都是无序的），使得第一组中各记录的键值均小
于或等于该键值，第二组中各记录的键值均大于该键值。然
后把该记录就排在这两组的中间（这也是该记录最终的位
置）。此称为一趟分割，对所分成的两组再分别重复上述方
法，直到所有记录都排在适当位置为止。
14
§ 10.3.3 快速排序
(二 )分割算法
?一趟快速排序的具体做法是：设两个指针 i和 j，它们的初值
分别为 0,n-1，且把 a[0]送入工作单元 x中保存（选第一个记
录为标准），然后比较 a[j]和 x，若 a[j]>x，则 j减 1后继续与 x比
较，直至 r[j]＜ =x，然后，将 a[j]移至 a[i]的位置，令 i加 1，接
着进行 a[i]和 x的比较，若 a[i]<x，则令 x加 1，然后继续比较，
直至满足 a[i]＞ =x，此时，将 a[i]移至 r[j]的位置，令 j减 1，之
后，重复上述过程，直至 i==j。此时 i便是记录 x所应在的位置。
15
§ 10.3.3 快速排序
(二 )分割算法
long SortPartition (in a[],long p1,long p2);
{//对 a[p1]—a[p2]进行分割, 返回分割点
long i,j;
int x;
i =p1;
j =p2;
x =a[i];
16
§ 10.3.3 快速排序
(二 )分割算法
while (i<j)
{
while ( a[j]>x && i<j ) j--
if (i<j) {a[j]=a[j]; i++;}
while (a[i]<=x && i<j ) i++;
if (i<j) {a[j] =a[i]; j--;}
}
a[i]=x;
return i;
}
17
§ 10.3.3 快速排序
(二 )分割算法
初始关键字 70 73 69 23 93 18 11 68
一次交换之后 68 73 69 23 93 18 11 70
二次交换之后 68 70 69 23 93 18 11 73
三次交换之后 68 11 69 23 93 18 70 73
68 11 69 23 93 18 70 73
68 11 69 23 93 18 70 73
四次交换之后 68 11 69 23 70 18 93 73
五次交换之后 68 11 69 23 18 70 93 73
18
§ 10.3.3 快速排序
(三 )快速排序递归程序
longSortQuick(ing a[],long p1,long p2)
{
long p;
if (p1<p2)
{
p = SortPartition(a,p1,p2);
SortQuick(a,p1,p-1);
SortQuick(a,p+1,p2);
return p2-p1+1;
}
return 0;
}
19
(四 )快速排序非递归算法
long QuickSort2(int a[],long p1,long p2)
{
long *s; top
long i,j;
s=new long[p2-p1+1];
if (s==NULL) return -1;
top=0;
top++; s[top]=p1;
top++; s[top]=p2;
while (top!=0)
{
j = s[top]; top--;
i = s[top]; top--;
20
while (i<j)
{
p = SortPartition(a,i,j);
if (p-i<j-p)
{//先分割前部,后部进栈
top++; s[top] = p+1;
top++; s[top] = j;
j = p-1;
}
else
{//先分割后部,前部进栈
top++; s[top] = i;
top++; s[top] = p-1;
i = p+1;
}
}// while (i<j)
}// while (top!=0)
return p2-p1+1;
}
21
§ 10.3.3 快速排序
(四 )快速排序非递归算法
初始关键字 [70 73 69 23 93 18 11 68]
第一趟排序之后 [68 11 69 23 18] 70 [93 73]
第二趟排序之后 [18 11 23] 68 [69] 70 [93 73]
第三趟排序之后 11 18 23 68 69 70 [93 73]
第四趟排序之后 11 18 23 68 69 70 73 93
从平均时间性能而言，快速排序最佳，其时间复
杂性为 O（ nlog2n）
但在最坏情况下，即对几乎是排序好的输入序列，
该算法的效率很低，近似于 O（ n2）
22
§ 10.4 选择排序
? 基本思想是：
依次选出第 1小、第 2小,… 的记录
? 主要有两种形式的的选择排序：
– 直接选择排序
– 堆排序。
23
§ 10.4.1 直接选择排序
直接选择排序算法如下：
longSortSelection(int a[],long p1,long p2)
{
int t;
long i,j,k;
for (i=p1; i<p2; i++)
{
k=i;
for (j=i+1; j<=p2; j++)
if (a[k]>a[j]) k = j;
t = a[k];
a[k]=a[i];
a[i]=t;
}
return p2-p1+1;
}
24
§ 10.4.1 直接选择排序
直接选择排序进行排序, 过程如下 （ 方拓号表示无序区 ）,
[8 4 3 6 9 2 7]
2 [4 3 6 9 8 7]
2 3 [4 6 9 8 7]
2 3 4 [6 9 8 7]
2 3 4 6 [9 8 7]
2 3 4 6 7 [8 9]
2 3 4 6 7 8 [9]
选择排序算法时间复杂性为 O（ n2） 。
25
§ 10.4.2 堆排序
(一）基本思想
?树形选择排序的基本思想是：
– 首先对 n个记录的键值进行两两比较。然后在其中 [n/2]个较小
者之间再进行两两比较。如此重复，直至选出最小键值的记
录为止。
– 可用一棵树来表示这一排序过程 。 树中的 n个叶子代表待排序
记录的键值 。 叶子上面一层是叶子两两比较的结果 。 依此类
推, 树根表示最后选择出来最小的关键字 。
– 在选择出最小键值后，将其输出，然后，再在剩余的树结点
中，按同样的方法选择最小者，这样，也是经过 n-1选择，就
将记录按升序输出了。
26
§ 10.4.2 堆排序
(一）基本思想
?堆结构：即前面介绍的顺序二叉树
?堆,若某堆结构中，每个结点的值均小于它的两
个儿子的值，则称该堆结构为堆。
27
§ 10.4.2 堆排序
10
20 18
29 32 19 22
40 50 39
10 20 18 29 32 19 22 40 50 39
图 -堆示例
28
§ 10.4.2 堆排序
(一）基本思想
?堆排序的基本方法可描述为：
1 [建堆 ] 将原始数据调整为堆；
2 [输出 ] 输出堆顶元素
3 [调整 ] 将堆结构中剩余元素重新调整为堆
4 [判断 ] 若全部元素均已输出，则结束，输出次序即为排
序次序。否则，转 2;
29
§ 10.4.2 堆排序
(二） 堆调整
?堆调整是针对这样的堆结构：堆顶（根）的左右子树都
是堆，但考虑堆顶后，就可能不满足堆的定义了。
堆调整可递归地描述为：
long HeapShift(int a[],long p1,long p2)
{
long j;
int x;
if (p1>=p2) return 0; //只有一个元素或无元素
30
§ 10.4.2 堆排序
(二） 堆调整
j=2*p1;
if (j+1<=p2) //令 j为 p1的值最小的儿子
if (a[j]>a[j+1]) j = j+1;
if (a[p1]<a[j]) return 1;
x=a[j];
a[i]=a[p1];
a[p1]=x;
return 1+HeapShift(a,j,p2);
}
31
§ 10.4.2 堆排序
(二） 堆调整
它的非递归程序为：
longHeapShift(int a[],long p1,long p2)
{
long i,j,cnt=0;
if (p1>=p2) return 0; //只有一个元素或无元素
i= p1;
j=2*i;
if (j+1<=p2) //令 j为 i的值最小的儿子
if (a[j]>a[j+1]) j = j+1;
32
§ 10.4.2 堆排序
(三） 建堆
?从最后一个叶子的父亲结点开始, 按从下到上, 从右到
左的次序, 对各结点 (k,k-1,…,1)逐步调用 HeapShift()
?该过程的程序实现为：
for (i=p2/2; i>=0; i--) HeapShift(a,i,p2);
33
§ 10.4.2 堆排序
(四） 堆排序
?每次, 输出, 元素, 我们并不真正输出, 可以只是将它与当前堆尾
元素交换位置
?下次, 输出, 和, 调整, 时, 我们将当前堆的堆尾视为上次堆尾的
上个元素 （ 堆顶不变 ）, 然后对新的堆进行, 输出, 和, 调整,
?具体过程如下：
for (i=p2; i>p1; i--) //每次对 a[1]—a[i]对应的堆进行输出, 调整
{
交换 a[p1]与当前堆尾 a[i]
HeapShift(a,p1,i-1); //调整新堆
}
34
§ 10.4.2 堆排序
(四） 堆排序
?完整的堆排序程序如下：
long SortHeap(int a[],long p1,long p2)
{
long i;
int x;
for (i=p2/2; i>=p1; i--) HeapShift(a,i,p2);
for (i=p2; i>p1; i--) //每次对 a[1]—a[i]对应的堆进行输出, 调整
{
x = a[p1];
a[p1] = a[i];
a[i] = x;
HeapShift(a,p1,i-1); //调整新堆
}
return p2-p1+1;
}
对于 n个记录进行排序所需的时间是
O（ nlog2n）。在最坏情况下，其时
间复杂性也为 O（ nlog2n）
35
§ 10.5 归并排序
?归并排序是一种基于合并有序段的排序方法
?对初始记录集，将每个记录视为一个独立的有序段，通
过逐步合并各有序段实现对整个记录集的排序
?归并排序的基础是合并
36
§ 10.5.1 二段合并
?把两个有序段中的记录分别记为
as,…, am 和 am+1,…, an
?两个有序子序列的合并就是形成第三个有序段
bs,…, bn
?算法的非形式描述如下：
设 i,j分别表示两个段中记录的下标 。
① 当 i≤m,且 j≤n时, 比较 a[i]和 a[j]键值的大小, 将其中键值较小的记
录取出并顺序送入 b[],同时修改 i或 j值；
②当 i＞ m或 j＞ n时，将另一子序列中的剩余部分照抄到第三个序列的
末尾。
37
§ 10.5.1 二段合并
void MergeSorted(int a[],int b[],long s,long m,long n)
{
long i,j,k;
i=s; j=m+1; k=0;
while (i<=m && j<=n)
if (a[i] <= a[j]) b[k++]=a[i++];
else b[k++]=a[j++];
while (i<=m) b[k++]=a[i++];
while (j<=n) b[k++]=a[j++];
return;
}
此算法的执行时间为 O（ n-s+1）
38
§ 10.5.1 二段合并
?设某记录集已分段有序, 除最后一个段外, 其他各段长度均相等
void MMergeSorted(int a[],long p1,longp2,long len,int b[])
{//a[p1]—a[p2]中, 每 len个元素为一个有序段, 将其合并为一个一序
段, 存入 b[]
long i,j,n,k,
i=p1;
n=p2-p1+1;
k=0;
此算法的执行时间为 O（ n-s+1）
39
§ 10.5.1 二段合并
while (i+2*len <= n)
{//当从 i起, 后面有完整的两段时, 合并之
MergeSorted(a,i,i+len-1,i+2*len-1,b+k);
i += 2*len;
k+=2*len;
}
if (i+len<n) //剩两段, 但最后的段不足 len
MergeSorted(a,i,i+len-1,p2,b+k );
else //剩一段
for (j=i; j<=p2; j++) b[k++]=a[j];
}
此算法的执行时间为 O（ n-s+1）
40
§ 10.5.2 二路归并排序
?利用二个有序序列的合并来实现归并排序
?基本思想是：
– 如果序列中有 n个记录, 可以先把它看成 n个子序列
?先将每相邻的两个子序列合并, 得到 [n/2]个较大的有序
子序列, 每个子序列包含 2个记录
?再将这些子序列两两合并, 得到 [[n/2]/2]个有序子序列
?如此反复, 直到最后合并成一个有序序列
41
§ 10.5.2 二路归并排序
[26] [5] [77] [1] [61] [11] [59] [15] [48] [19]
[ 5 26 ] [ 1 77 ] [ 11 61 ] [15 59 ] [ 19 48 ]
[ 1 5 26 77 ] [11 15 59 61 ] [ 19 48 ]
[ 1 5 11 15 26 59 61 77 ] [19 48]
[ 1 5 11 15 19 26 48 59 61 77 ]
42
§ 10.5.2 二路归并排序
二路归并排序算法如下：
void SortMerge(int a[],long p1,long p2,int b[])
{
long len;
while (len<p2-p1+1)
{
MMergeSorted(a,p1,p2,len,b);
i = i*2;
MMergeSorted(b,0,p2-p1,len,a+p1);
}
}
43
§ 10.6 外排序简介
?处理大型数据文件的排序技术
?可以分为磁盘文件排序和磁带文件排序两大类
?外部排序基本上由两个相对独立的阶段组成
– 首先, 按可用内存大小, 将外存上含 n个记录的文件分成若干
长度为 h的子文件, 依次读入内存并利用有效的内部排序方法
对它们进行排序, 并将排序后得到的有序子文件重新写入外
存
– 然后, 对这些归并段进行逐趟归并, 使归并段 （ 有序的子文
件 ） 逐渐由小到大, 直至得到整个有序文件为止
第 10 章 排序算法
2
§ 10.1 概述
? 排序的主要目的是便于以后在已排序的集合中查找检
索某一成员
? 若干概念
– 关键字
– 排序
– 排序的稳定性
– 内排序
– 外排序
– 多键排序
3
§ 10.1 概述
? 排序方法进行分类
– 插入排序
– 交换排序
– 选择排序
– 归并排序
– 分配排序
4
§ 10.1 概述
? 算法的时间复杂性
– 通常只考虑键值的比较次数和记录的移动次数
? 评价排序的另一个主要标准是执行算法所需的附加空
间
5
§ 10.2 插入排序
? 插入排序的基本方法是：每步将一个待排序的记录按
其关键字的大小插到前面已经排序的序列中的适当位
置，直到全部记录插入完毕为止。
6
§ 10.2.1 直接插入排序
初始键值序列
[46] 58 15 45 90 18 10 62
i=2 [46 58] 15 45 90 18 10 62
i=3 [15 46 58] 45 90 18 10 62
i=4 [15 45 46 58] 90 18 10 62
i=5 [15 45 46 58 90] 18 10 62
i=6 [15 18 45 46 58 90] 10 62
i=7 [10 15 18 45 46 58 90] 62
i=8 [10 15 18 45 46 58 62 90]
图 10-1直接插入排序过程示例
7
§ 10.2.1 直接插入排序
?可以将插入排序粗略地描述为：
SortInsertion(int a[],long n)
{
for (i=1; i<n; i++)
将 a[i]插入到 a[0]—a[i-1]中, 并使其保持有序
}
8
插入排序的程序：
int SortInsertion(int a[],long n)
{
int x,i,,j;
for (i=1; i<n; i++)
{
x=a[i];
j=i-1;
while (j>=0 && x<a[j])
{
a[j+1] = a[j];
j--;
}
a[j+1] = x;
} //for
return 0;
}
9
§ 10.2.2 其他插入排序算法
?除了直接插入排序外, 还有其他形式的插入排序, 如折半插入
排序, 表插入排序和希尔排序等 。
?它们是对直接插入排序的改进 。 改进的关键点是, 如何尽快地
找到插入位置 。
10
§ 10.3 交换排序
?所谓交换, 就是根据记录集中两个记录键值的比较结果来对换
这两个记录在序列中的位置
?交换排序的特点是：将键值较大的记录向记录集的一端移动,
键值较小的记录向另一端移动 。
11
§ 10.3.1 冒泡排序
? 设初始记录集为
20 30 10 45 33 22 55 50
? 则第一趟冒泡的过程为：
20 30 10 45 33 22 55 50 //20与 30比较, 未交换
20 10 30 45 33 22 55 50 //30与 10比较, 交换
20 10 30 45 33 22 55 50 //30与 45比较, 未交换
20 10 30 33 45 22 55 50 //45与 33比较, 交换
20 10 30 33 22 45 55 50 //45与 22比较, 交换
20 10 30 33 22 45 55 50 //45与 55比较, 未交换
20 10 30 33 22 45 50 55 //55与 50比较, 交换
12
§ 10.3.1 冒泡排序
?每趟的结果
10 20 30 22 33 45 50 55 //第 2趟
10 20 22 30 33 45 50 55 //第 3趟
10 20 22 30 33 45 50 55 //第 4趟
10 20 22 30 33 45 50 55 //第 5趟
10 20 22 30 33 45 50 55 //第 6趟
10 20 22 30 33 45 50 55 //第 7趟
10 20 22 30 33 45 50 55 //第 8趟
13
§ 10.3.3 快速排序
(一 )基本思想
?基本思想是：在待排序的 n个记录中任取一个记录（例如就
取第一个记录），以该记录的键值为标准，将所有记录分为
两组（一般都是无序的），使得第一组中各记录的键值均小
于或等于该键值，第二组中各记录的键值均大于该键值。然
后把该记录就排在这两组的中间（这也是该记录最终的位
置）。此称为一趟分割，对所分成的两组再分别重复上述方
法，直到所有记录都排在适当位置为止。
14
§ 10.3.3 快速排序
(二 )分割算法
?一趟快速排序的具体做法是：设两个指针 i和 j，它们的初值
分别为 0,n-1，且把 a[0]送入工作单元 x中保存（选第一个记
录为标准），然后比较 a[j]和 x，若 a[j]>x，则 j减 1后继续与 x比
较，直至 r[j]＜ =x，然后，将 a[j]移至 a[i]的位置，令 i加 1，接
着进行 a[i]和 x的比较，若 a[i]<x，则令 x加 1，然后继续比较，
直至满足 a[i]＞ =x，此时，将 a[i]移至 r[j]的位置，令 j减 1，之
后，重复上述过程，直至 i==j。此时 i便是记录 x所应在的位置。
15
§ 10.3.3 快速排序
(二 )分割算法
long SortPartition (in a[],long p1,long p2);
{//对 a[p1]—a[p2]进行分割, 返回分割点
long i,j;
int x;
i =p1;
j =p2;
x =a[i];
16
§ 10.3.3 快速排序
(二 )分割算法
while (i<j)
{
while ( a[j]>x && i<j ) j--
if (i<j) {a[j]=a[j]; i++;}
while (a[i]<=x && i<j ) i++;
if (i<j) {a[j] =a[i]; j--;}
}
a[i]=x;
return i;
}
17
§ 10.3.3 快速排序
(二 )分割算法
初始关键字 70 73 69 23 93 18 11 68
一次交换之后 68 73 69 23 93 18 11 70
二次交换之后 68 70 69 23 93 18 11 73
三次交换之后 68 11 69 23 93 18 70 73
68 11 69 23 93 18 70 73
68 11 69 23 93 18 70 73
四次交换之后 68 11 69 23 70 18 93 73
五次交换之后 68 11 69 23 18 70 93 73
18
§ 10.3.3 快速排序
(三 )快速排序递归程序
longSortQuick(ing a[],long p1,long p2)
{
long p;
if (p1<p2)
{
p = SortPartition(a,p1,p2);
SortQuick(a,p1,p-1);
SortQuick(a,p+1,p2);
return p2-p1+1;
}
return 0;
}
19
(四 )快速排序非递归算法
long QuickSort2(int a[],long p1,long p2)
{
long *s; top
long i,j;
s=new long[p2-p1+1];
if (s==NULL) return -1;
top=0;
top++; s[top]=p1;
top++; s[top]=p2;
while (top!=0)
{
j = s[top]; top--;
i = s[top]; top--;
20
while (i<j)
{
p = SortPartition(a,i,j);
if (p-i<j-p)
{//先分割前部,后部进栈
top++; s[top] = p+1;
top++; s[top] = j;
j = p-1;
}
else
{//先分割后部,前部进栈
top++; s[top] = i;
top++; s[top] = p-1;
i = p+1;
}
}// while (i<j)
}// while (top!=0)
return p2-p1+1;
}
21
§ 10.3.3 快速排序
(四 )快速排序非递归算法
初始关键字 [70 73 69 23 93 18 11 68]
第一趟排序之后 [68 11 69 23 18] 70 [93 73]
第二趟排序之后 [18 11 23] 68 [69] 70 [93 73]
第三趟排序之后 11 18 23 68 69 70 [93 73]
第四趟排序之后 11 18 23 68 69 70 73 93
从平均时间性能而言，快速排序最佳，其时间复
杂性为 O（ nlog2n）
但在最坏情况下，即对几乎是排序好的输入序列，
该算法的效率很低，近似于 O（ n2）
22
§ 10.4 选择排序
? 基本思想是：
依次选出第 1小、第 2小,… 的记录
? 主要有两种形式的的选择排序：
– 直接选择排序
– 堆排序。
23
§ 10.4.1 直接选择排序
直接选择排序算法如下：
longSortSelection(int a[],long p1,long p2)
{
int t;
long i,j,k;
for (i=p1; i<p2; i++)
{
k=i;
for (j=i+1; j<=p2; j++)
if (a[k]>a[j]) k = j;
t = a[k];
a[k]=a[i];
a[i]=t;
}
return p2-p1+1;
}
24
§ 10.4.1 直接选择排序
直接选择排序进行排序, 过程如下 （ 方拓号表示无序区 ）,
[8 4 3 6 9 2 7]
2 [4 3 6 9 8 7]
2 3 [4 6 9 8 7]
2 3 4 [6 9 8 7]
2 3 4 6 [9 8 7]
2 3 4 6 7 [8 9]
2 3 4 6 7 8 [9]
选择排序算法时间复杂性为 O（ n2） 。
25
§ 10.4.2 堆排序
(一）基本思想
?树形选择排序的基本思想是：
– 首先对 n个记录的键值进行两两比较。然后在其中 [n/2]个较小
者之间再进行两两比较。如此重复，直至选出最小键值的记
录为止。
– 可用一棵树来表示这一排序过程 。 树中的 n个叶子代表待排序
记录的键值 。 叶子上面一层是叶子两两比较的结果 。 依此类
推, 树根表示最后选择出来最小的关键字 。
– 在选择出最小键值后，将其输出，然后，再在剩余的树结点
中，按同样的方法选择最小者，这样，也是经过 n-1选择，就
将记录按升序输出了。
26
§ 10.4.2 堆排序
(一）基本思想
?堆结构：即前面介绍的顺序二叉树
?堆,若某堆结构中，每个结点的值均小于它的两
个儿子的值，则称该堆结构为堆。
27
§ 10.4.2 堆排序
10
20 18
29 32 19 22
40 50 39
10 20 18 29 32 19 22 40 50 39
图 -堆示例
28
§ 10.4.2 堆排序
(一）基本思想
?堆排序的基本方法可描述为：
1 [建堆 ] 将原始数据调整为堆；
2 [输出 ] 输出堆顶元素
3 [调整 ] 将堆结构中剩余元素重新调整为堆
4 [判断 ] 若全部元素均已输出，则结束，输出次序即为排
序次序。否则，转 2;
29
§ 10.4.2 堆排序
(二） 堆调整
?堆调整是针对这样的堆结构：堆顶（根）的左右子树都
是堆，但考虑堆顶后，就可能不满足堆的定义了。
堆调整可递归地描述为：
long HeapShift(int a[],long p1,long p2)
{
long j;
int x;
if (p1>=p2) return 0; //只有一个元素或无元素
30
§ 10.4.2 堆排序
(二） 堆调整
j=2*p1;
if (j+1<=p2) //令 j为 p1的值最小的儿子
if (a[j]>a[j+1]) j = j+1;
if (a[p1]<a[j]) return 1;
x=a[j];
a[i]=a[p1];
a[p1]=x;
return 1+HeapShift(a,j,p2);
}
31
§ 10.4.2 堆排序
(二） 堆调整
它的非递归程序为：
longHeapShift(int a[],long p1,long p2)
{
long i,j,cnt=0;
if (p1>=p2) return 0; //只有一个元素或无元素
i= p1;
j=2*i;
if (j+1<=p2) //令 j为 i的值最小的儿子
if (a[j]>a[j+1]) j = j+1;
32
§ 10.4.2 堆排序
(三） 建堆
?从最后一个叶子的父亲结点开始, 按从下到上, 从右到
左的次序, 对各结点 (k,k-1,…,1)逐步调用 HeapShift()
?该过程的程序实现为：
for (i=p2/2; i>=0; i--) HeapShift(a,i,p2);
33
§ 10.4.2 堆排序
(四） 堆排序
?每次, 输出, 元素, 我们并不真正输出, 可以只是将它与当前堆尾
元素交换位置
?下次, 输出, 和, 调整, 时, 我们将当前堆的堆尾视为上次堆尾的
上个元素 （ 堆顶不变 ）, 然后对新的堆进行, 输出, 和, 调整,
?具体过程如下：
for (i=p2; i>p1; i--) //每次对 a[1]—a[i]对应的堆进行输出, 调整
{
交换 a[p1]与当前堆尾 a[i]
HeapShift(a,p1,i-1); //调整新堆
}
34
§ 10.4.2 堆排序
(四） 堆排序
?完整的堆排序程序如下：
long SortHeap(int a[],long p1,long p2)
{
long i;
int x;
for (i=p2/2; i>=p1; i--) HeapShift(a,i,p2);
for (i=p2; i>p1; i--) //每次对 a[1]—a[i]对应的堆进行输出, 调整
{
x = a[p1];
a[p1] = a[i];
a[i] = x;
HeapShift(a,p1,i-1); //调整新堆
}
return p2-p1+1;
}
对于 n个记录进行排序所需的时间是
O（ nlog2n）。在最坏情况下，其时
间复杂性也为 O（ nlog2n）
35
§ 10.5 归并排序
?归并排序是一种基于合并有序段的排序方法
?对初始记录集，将每个记录视为一个独立的有序段，通
过逐步合并各有序段实现对整个记录集的排序
?归并排序的基础是合并
36
§ 10.5.1 二段合并
?把两个有序段中的记录分别记为
as,…, am 和 am+1,…, an
?两个有序子序列的合并就是形成第三个有序段
bs,…, bn
?算法的非形式描述如下：
设 i,j分别表示两个段中记录的下标 。
① 当 i≤m,且 j≤n时, 比较 a[i]和 a[j]键值的大小, 将其中键值较小的记
录取出并顺序送入 b[],同时修改 i或 j值；
②当 i＞ m或 j＞ n时，将另一子序列中的剩余部分照抄到第三个序列的
末尾。
37
§ 10.5.1 二段合并
void MergeSorted(int a[],int b[],long s,long m,long n)
{
long i,j,k;
i=s; j=m+1; k=0;
while (i<=m && j<=n)
if (a[i] <= a[j]) b[k++]=a[i++];
else b[k++]=a[j++];
while (i<=m) b[k++]=a[i++];
while (j<=n) b[k++]=a[j++];
return;
}
此算法的执行时间为 O（ n-s+1）
38
§ 10.5.1 二段合并
?设某记录集已分段有序, 除最后一个段外, 其他各段长度均相等
void MMergeSorted(int a[],long p1,longp2,long len,int b[])
{//a[p1]—a[p2]中, 每 len个元素为一个有序段, 将其合并为一个一序
段, 存入 b[]
long i,j,n,k,
i=p1;
n=p2-p1+1;
k=0;
此算法的执行时间为 O（ n-s+1）
39
§ 10.5.1 二段合并
while (i+2*len <= n)
{//当从 i起, 后面有完整的两段时, 合并之
MergeSorted(a,i,i+len-1,i+2*len-1,b+k);
i += 2*len;
k+=2*len;
}
if (i+len<n) //剩两段, 但最后的段不足 len
MergeSorted(a,i,i+len-1,p2,b+k );
else //剩一段
for (j=i; j<=p2; j++) b[k++]=a[j];
}
此算法的执行时间为 O（ n-s+1）
40
§ 10.5.2 二路归并排序
?利用二个有序序列的合并来实现归并排序
?基本思想是：
– 如果序列中有 n个记录, 可以先把它看成 n个子序列
?先将每相邻的两个子序列合并, 得到 [n/2]个较大的有序
子序列, 每个子序列包含 2个记录
?再将这些子序列两两合并, 得到 [[n/2]/2]个有序子序列
?如此反复, 直到最后合并成一个有序序列
41
§ 10.5.2 二路归并排序
[26] [5] [77] [1] [61] [11] [59] [15] [48] [19]
[ 5 26 ] [ 1 77 ] [ 11 61 ] [15 59 ] [ 19 48 ]
[ 1 5 26 77 ] [11 15 59 61 ] [ 19 48 ]
[ 1 5 11 15 26 59 61 77 ] [19 48]
[ 1 5 11 15 19 26 48 59 61 77 ]
42
§ 10.5.2 二路归并排序
二路归并排序算法如下：
void SortMerge(int a[],long p1,long p2,int b[])
{
long len;
while (len<p2-p1+1)
{
MMergeSorted(a,p1,p2,len,b);
i = i*2;
MMergeSorted(b,0,p2-p1,len,a+p1);
}
}
43
§ 10.6 外排序简介
?处理大型数据文件的排序技术
?可以分为磁盘文件排序和磁带文件排序两大类
?外部排序基本上由两个相对独立的阶段组成
– 首先, 按可用内存大小, 将外存上含 n个记录的文件分成若干
长度为 h的子文件, 依次读入内存并利用有效的内部排序方法
对它们进行排序, 并将排序后得到的有序子文件重新写入外
存
– 然后, 对这些归并段进行逐趟归并, 使归并段 （ 有序的子文
件 ） 逐渐由小到大, 直至得到整个有序文件为止
