2001 -- 12 --31
华中科技大学计算机学院 (11)数据结构第十章 内排序
10.1 概述
1.排序 ----将文件或表中的记录，通过某种方法整理成按关键字大小次序排列的处理过程。
假定 n个记录的文件为
(R1,R2,...,Rn)
对应的关键字为
(K1,K2,...,Kn)
则排序是确定如下一个排列
p1,p2,...,pn
使得
Kp1≤K p2≤,..≤ Kpn
从而得到一个 有序文件
(Rp1,Rp2,...Rpn)
学生成绩表
20051 刘大海 80 75
20042 王 伟 90 83
20066 吴晓英 82 88
20038 刘 伟 80 70
20052 王 洋 60 70
1
2
3
4
5
学 号 姓 名 数学 外语
20038 刘 伟 80 70
20042 王 伟 90 83
20051 刘大海 80 75
20052 王 洋 60 70
20066 吴晓英 82 88
学 号 姓 名 数学 外语
20052 王 洋 60 70
20051 刘大海 80 75
20038 刘 伟 80 70
20066 吴晓英 82 88
20042 王 伟 90 83
20042 王 伟 90 83 173
20066 吴晓英 82 88 170
20051 刘大海 80 75 155
20038 刘 伟 80 70 150
20052 王 洋 60 70 130
1
2
3
4
5
学 号 姓 名 数学 外语 学 号 姓 名 数学 外语 总分
1
2
3
4
5
1
2
3
4
5
(a) 无序表 (b) 按 学号排列 的 有序表
(c) 按 数学成绩排列 的 有序表 (d) 按总分 成绩排列 的 有序表
2.什么是 排序的稳定性假设在待排序的文件中，存在两个具有相同关键字的记录 R(i)与 R(j),其中 R(i)位于 R(j)之前。在用某种排序法排序之后,R(i)仍位于 R(j)之前，则称这种排序方法是 稳定的 ；否则，称这种排序方法是 不稳定的 。
例 数列
(10,25,22,42,25,30,18) (10,18,22,25,25,30,42)
(10,25,22,42,25,30,18) (10,18,22,25,25,30,42)
稳定 的排序不稳定 的排序
20051 刘大海 80 75
20042 王 伟 90 83
20066 吴晓英 82 88
20038 刘 伟 80 70
20052 王 洋 60 70
1
2
3
4
5
学 号 姓 名 数学 外语
20052 王 洋 60 70
20038 刘 伟 80 70
20051 刘大海 80 75
20066 吴晓英 82 88
20042 王 伟 90 83
学 号 姓 名 数学 外语
1
2
3
4
5
(e) 按 数学成绩排列的有序表不稳定的排序
3.内部排序 (内排序 )----在计算机内存中进行的排序外部排序 (外排序 )----借助计算机外存进行的排序
4.待排序的记录和顺序表 (文件 )的数据类型
#define MAXSIZE 20 //最大长度
typedef int KeyType； //关键字类型
typedef struct //记录类型
{ KeyType key； //关键字
InfoType otherinfo； //其它数据类型
}RecType； //记录类型名
typedef struct
{ RecType r[MAXSIZE+1]； //r[0]用作监视哨
int length； //实际表长 length≤MAXSIZE
}SeqList； //表和表长合并为 SeqList
或,//表和表长分别定义和说明
RecType r[MAXSIZE+1]； //r[0]用作监视哨
int length； //实际表长 length≤MAXSIZE
5.排序算法分析
(1)时间复杂度
● 对 n个记录排序，所需 比较关键字的次数 ；
最好情况；最坏情况；平均情况
● 对 n个记录排序，所需 移动记录的次数 ；
最好情况；最坏情况；平均情况
(2)空间复杂度排序过程中，除文件中的记录所占的空间外，
所需的 辅助存储空间 的大小。
6.内排序方法
(1)对顺序表的排序
● 插入排序：直接插入排序；
折半插入排序； 2-路插入排序；表插入排序；
希尔 (Shell)排序 ；
● 选择排序：简单选择 /选择排序；
树形选择排序；堆排序
● 归并排序
2-路归并排序
k-路归并排序
● 交换排序冒泡排序：单向冒泡排序，双向冒泡排序快速排序
● 基数排序多关键字排序最高位优先法最低位优先法链式基数排序
(2)对单链表的 排序直接插入,简单选择,冒泡排序,基数排序
10.2 插入排序算法基本思想将待排序的记录插入到已排序的子文件中去，使得插入之后得到的子文件仍然是有序子文件。插入一个记录，首先要对有序子文件进行查找，以确定这个记录的插入位置。按查找方式的不同，插入排序又可以分为线性插入排序和折半插入排序，前者使用顺序查找，后者使用折半查找。
1.直接插入排序 (线性插入排序 )
设待排序的文件为 (r[1],r[2],...,r[n])
关键字为 (r[1].key,r[2].key,...,r[n].key)
首先,将初始文件中的记录 r[1]看作有序子文件；
第 1遍：将 r[2]插入有序子文件中：若 r[2].key<r[1].key，
则 r[2]插在 r[1]之前；否则，插在 r[1]的后面。
第 2遍：将记录 r[3]插入前面已有 2个记录的有序子文件中，
得到 3个记录的有序子文件。
以此类推，依次插入 r[4],...,r[n],最后得到 n个记录的递增有序文件。
例,直接插入排序,设 K0为 "监视哨,
K0 K1 K2 K3 K4 K5 K6
初始关键字,( 43 ) 21 89 15 43 28
(43后移 ) ┌─┘
↓
第 1遍 (趟 )排序后,21 ( 21 43 ) 89 15 43 28
(不后移 ) │
↓
第 2遍排序后,89 ( 21 43 89 ) 15 43 28
(89,43,21后移 ) ┌──────┘
↓
第 3遍排序后,15 ( 15 21 43 89 ) 43 28
(89后移 ) ┌─┘
↓
第 4遍排序后,43 ( 15 21 43 43 89 ) 28
(89,43,43后移 ) ┌──────┘
↓
第 5遍排序后,28 ( 15 21 28 43 43 89)
直接插入排序算法
void InsertSort(RecType r[],int n）
// 对数组 r[1..n]中的 n个记录作插入排序
{ int i,j；
for (i=2； i<=n； i++)
{ r[0]=r[i]； //待插记录 r[i]存入监视哨中
j=i-1； //从 r[i-1]开始向左扫描
while(r[0].key<r[j].key)
{ r[j+1]=r[j]； //记录后移
j--； //继续向左扫描
}
r[j+1]=r[0]； //插入记录 r[0],即原 r[i]
}
}
直接插入排序算法分析：
(1)最好情况,原 n个记录递增有序：
比较关键字 n-1次移动记录 2(n-1)次
ri r1 r2 ……
…
ri-1 ri … rn
r[0] r[1] r[2] r[i-1] r[i] r[n]
(2)最坏情况,原 n个记录递减有序：
比较关键字的次数,
n
∑ i = 2+3+...+n =(n-1)(n+2)/2 = O(n2)
i=2
移动记录的次数 (个数 ):
n
∑ (i-1+2) = 3+4+...+(n+1)
i=2
=(n-1)(n+4)/2 次 = O(n2)
ri r1 r2 ……
…
ri-1 ri … rn
r[0] r[1] r[2] r[i-1] r[i] r[n]
ri r1’ r2 ’ ……
…
ri-1 ’ ri … rn
r[0] r[1] r[2] r[i-1] r[i] r[n]
(3)平均比较关键字的次数约 为,
n n i+1
∑ (1+2+… +i)/i= ∑ --- =(3+4+...+(n+1))/2
i=2 i=2 2
=(n-1)(n+4)/4=O(n2)
平均移动记录的次数约为,
n n (i+3)
∑ ((0+2)+(1+2)+… +(i-1+2))/i=∑ ----- =(5+6+...+(n+3))/2
i=2 i=2 2
=(n-1)(n+8)/2=O(n2)
故,时间复杂度为 O(n2)。
(4) 只需 少量中间变量 作为辅助空间。
(5) 算法是 稳定 的。
10.3 选择排序
1.简单 选择 (选择排序 )
算法基本思想设待排序的文件为 (r[1],r[2],...,r[n]),关键字为
(r[1].key,r[2].key,...,r[n].key),
第 1趟 (遍 )：在 (r[1],r[2],...,r[n])中,选出关键字最小的记录 r[min].key,若 min<>1,则交换 r[1]和 r[min]；
需要进行 n-1次比较。
第 2趟 (遍 )：在 n-1个记录 (r[2],...,r[n])中,选出关键字最小的记录 r[min].key,若 min<>2,则交换 r[2]和 r[min]；
需要进行 n-2次比较。
.....,
第 n-1趟 (遍 )：在最后的 2个记录记录 (r[n-1],r[n])中,选出关键字最小的记录 r[min].key,若 min<>n-1,则交换 r[n-1]
和 min]； 需要进行 1次比较。
例,
k1 k2 k3 k4 k5 k6
初始关键字,（ 43 89 21 43 28 15 ）
↑ ↑
第 1遍排序后,15 （ 89 21 43 28 43 ）
↑ ↑
第 2遍排序后,15 21 （ 89 43 28 43 ）
↑ ↑
第 3遍排序后,15 21 28 （ 43 89 43 ）
↑↑
第 4遍排序后,15 21 28 43 （ 89 43 ）
↑ ↑
第 5遍排序后,15 21 28 43 43 89
简单选择排序算法：
void SelectSort(RecType r[],int n)
// 对数组 r[1..n]中 的 n个记录 作简单选择 排序
{ int i,j,min;
RecType x; //交换记录的中间变量
for (i=1;i<n;i++) //共 n-1趟 (遍 )
{ min=i; //r[i]为 最小记录 r[min]
for (j=i+1;j<=n;j++)
if (r[j].key<r[min].key)
min=j; //修改 min
if (min!=i) //若 r[min]不是 r[i]
{ x=r[min]; //交换 r[min]和 r[i]
r[min]=r[i]; r[i]=x;
}
}
}
算法分析：
(1)比较次数,在任何情况下,均为
n-1
∑ (n－ i)＝ (n-1)+(n-2)+...+1i=1
＝ n(n-1)/2 ＝ O(n2)
(2)交换记录的次数在最好情况下,原 n个记录递增有序：
不移动记录 。
在最 坏 情况下,每次都要交换数据 （ 不是递减有序 ）
共交换记录 n-1对,移动记录数 3(n-1)次 。
故,时间复杂度为 O(n2)。
(3)只需 少量中间变量 作为辅助空间 。
(4)算法是 不稳定 的 。
2.堆排序（ Heap Sort)
堆的定义,n个元素的序列 {k1,k2,…,k n} 当且仅当满足下关系时，
称之为 堆 。
ki ≤ k2i ki ≥ k2i
或
ki ≤ k2i+1 ki ≥ k2i+1
(i=1,2,…,?n/2?)
其中,前面一种称为小顶堆；
后面一种称为大顶堆。
n个元素的序列 {k1,k2,…,k n}可看成是一个结点个数为 n
的完全二叉数，若其为大顶堆，则 k1最大；若其为小顶堆，
则 k1最小。
例,序列 1,{96,83,27,38,11,09}
序列 2,{12,36,24,85,47,30,53,91}
96
83 27
38 11 09
36
85 47
91
24
30 53
12
序列 2的二叉树 (小 顶 )堆序列 1的二叉树 (大顶堆 )
通常,n个元素的序列 {k1,k2,…,k n} 不符合堆的定义，
所以，面临的第一个问题：
问题 1：如何将序列 {k1,k2,…,k n} 处理成（大顶）堆（初始化）？
问题 1一旦解决，得到规模为 n的堆，则 k1最大，将 k1与
kn互换，则最大的数已放置到最后，同时，剩下的序列
{k1,k2,…,k n-1}不是堆，如何将其重新处理成规模为 n-1的堆，
求取第二大的数据，以此类推，堆的规模逐步减小，直到求出第 n-1大的数据，完成递增排序。所以，面临的第二个问题是：
问题 2：如何在堆顶元素被替换后，调整剩余元素成为一个新的堆。
提示,根据上述过程描述,借助大顶堆可实现序列的递增排序；
借助小顶堆可实现序列的递减排序。
96
8327
11 3825 22
09
问题 2方法,某序列的堆形式,{96,27,83,25,22,11,38,09}
09
8327
11 3825 22
96
09
83
27
11 3825 22
96
09
83
27
11
38
25 22
96
除顶以外，
其它都符合堆的定义
83=max(83,27)
38=max(38,11)
s
s
s
j
j
j?s
j?s
typedef SqList HeapType; //采用顺序表存储表示
void HeapAdjust(HeapType &H,int s,int m)
//已知 H.r[s…m] 中记录的关键字除 H.r[s].key之外均满足堆的定义，本函数调整 H.r[s]的关键字,使 H.r[s…m] 成大顶堆。
{ rc=H.r[s]; //空出 s的记录位置
for(j=2*s; j<=m;j*=2) { //j<=m表示 s有左孩子序号 j=2*s
if (j<m && H.r[j].key< H.r[j+1].key) //j<m表示 s有右孩子 j+1
j++; //计算 s的具有较大关键字的孩子的序号 j
if (rc.key> H.r[j].key) // rc在 s的结点时满足结点定义，调整完毕
break;
H.rs[s]=H.r[j];s=j; //s的较大孩子上移，修改 s下移
} //正常结束时,s的结点无孩子结点。
H.r[s]=rc; }
38
97
7649
65
13 98
49
问题 1方法,建立序列,{49,38,65,97,76,13,27,49}
的初始堆。
1。对以最后一个结点（序号 n）
的双亲结点（序号 i=?n/2?）
为根的二叉树，进行堆调整。
38
97 76
49
65
13 98
49
2。对以序号序号 i=i-1的结点为双亲结点为根的二叉树，进行堆调整。
38
97 76
49
6513
98
49
3。对以序号序号 i=i-1的结点为双亲结点为根的二叉树，进行堆调整。
97
38 76
49
6513
98
49
97
38
7649 6513
98
49
97
38
7649 6513
98
49
97
38
7649 6513
49
98
97
38
7649 4913
65
98
4。对以序号序号 i=i-1的结点为双亲结点为根的二叉树，进行堆调整。此时 i已等于 1，调整完后,初始大顶堆建成 。
97
98
7649 4913
65
38
76
3849 4913
65
97
98
76
3849 9713
65
49
98
49
3849 9713
65
76
98
选择较小范围选择 较小范围调整调整
i>0
真假堆排序结束H.r[1]H.r[i]
调整以 i为根的二叉树
i--
n/2i
n?i
i>1
真假
i--
调整剩余 i-1个结点的二叉树初始化堆选择、调整
n-1次算法分析与评价：
对深度为 k的堆，调整算法进行的关键字比较次数至多为
2(k-1)次，
建立 n个元素的初始堆，调用 HeapAdjust算法?n/2?次，总共进行的关键字比较次数不超过 4n次。
n个结点的完全二叉树深度为 h=?log2n?+1
需要调整的层为 h-1层至 1层,以第 i层某结点为根的 二叉树深度对应为 h-i+1,第 i层结点最多为 2i-1个，故调整时比较关键字最多为：
2i-1*2*(h-i+1-1)= 2i*(h-i)
令 j=h-i,当 i=h-1时 j=1 当 i=1时 j=h-1
2h-j*j=2h-1*1+ 2h-2*2+… + 21*(h-1)=2h+1-2h-2
< 2h+1 =2?log2n?+2<=4* 2 log2n =4n
1
1hi
1
1hi
1
1
h
j
算法分析与评价 (续）,
n个结点的完全二叉树深度为?log2n?+1,选择调整过程 n-1
次，总共比较次数 至多为：
2 （?log2(n-1)?+?log2(n-2)?+… +?log22?)<2n(?log2n?)
最坏情况下，算法的时间复杂度为 O(4n+nlogn)?O(nlogn) ；
仅需要 一个记录大小 供交换用的辅助存储空间；
堆排序是 不稳定排序 。
堆排序对记录较少的文件不提倡，对 较大的文件很有效 ；
家庭作业
1.假定不使用 监视哨,试重写对顺序表直接插入排序的算法。
2.设单链表的结点结构为 (data,next),data为整型，试用插入排序的思想方法，对以 head为头指针的不带表头结点的单链表排序，写出算法。
3.设单链表的结点结构为 (data,next),data为整型，试用选择排序的思想方法，对以 head为头指针的不带表头结点的单链表排序，写出算法。
40 9 ∧30121520head
30 40 ∧2015129head
华中科技大学计算机学院 (11)数据结构第十章 内排序
10.1 概述
1.排序 ----将文件或表中的记录，通过某种方法整理成按关键字大小次序排列的处理过程。
假定 n个记录的文件为
(R1,R2,...,Rn)
对应的关键字为
(K1,K2,...,Kn)
则排序是确定如下一个排列
p1,p2,...,pn
使得
Kp1≤K p2≤,..≤ Kpn
从而得到一个 有序文件
(Rp1,Rp2,...Rpn)
学生成绩表
20051 刘大海 80 75
20042 王 伟 90 83
20066 吴晓英 82 88
20038 刘 伟 80 70
20052 王 洋 60 70
1
2
3
4
5
学 号 姓 名 数学 外语
20038 刘 伟 80 70
20042 王 伟 90 83
20051 刘大海 80 75
20052 王 洋 60 70
20066 吴晓英 82 88
学 号 姓 名 数学 外语
20052 王 洋 60 70
20051 刘大海 80 75
20038 刘 伟 80 70
20066 吴晓英 82 88
20042 王 伟 90 83
20042 王 伟 90 83 173
20066 吴晓英 82 88 170
20051 刘大海 80 75 155
20038 刘 伟 80 70 150
20052 王 洋 60 70 130
1
2
3
4
5
学 号 姓 名 数学 外语 学 号 姓 名 数学 外语 总分
1
2
3
4
5
1
2
3
4
5
(a) 无序表 (b) 按 学号排列 的 有序表
(c) 按 数学成绩排列 的 有序表 (d) 按总分 成绩排列 的 有序表
2.什么是 排序的稳定性假设在待排序的文件中，存在两个具有相同关键字的记录 R(i)与 R(j),其中 R(i)位于 R(j)之前。在用某种排序法排序之后,R(i)仍位于 R(j)之前，则称这种排序方法是 稳定的 ；否则，称这种排序方法是 不稳定的 。
例 数列
(10,25,22,42,25,30,18) (10,18,22,25,25,30,42)
(10,25,22,42,25,30,18) (10,18,22,25,25,30,42)
稳定 的排序不稳定 的排序
20051 刘大海 80 75
20042 王 伟 90 83
20066 吴晓英 82 88
20038 刘 伟 80 70
20052 王 洋 60 70
1
2
3
4
5
学 号 姓 名 数学 外语
20052 王 洋 60 70
20038 刘 伟 80 70
20051 刘大海 80 75
20066 吴晓英 82 88
20042 王 伟 90 83
学 号 姓 名 数学 外语
1
2
3
4
5
(e) 按 数学成绩排列的有序表不稳定的排序
3.内部排序 (内排序 )----在计算机内存中进行的排序外部排序 (外排序 )----借助计算机外存进行的排序
4.待排序的记录和顺序表 (文件 )的数据类型
#define MAXSIZE 20 //最大长度
typedef int KeyType； //关键字类型
typedef struct //记录类型
{ KeyType key； //关键字
InfoType otherinfo； //其它数据类型
}RecType； //记录类型名
typedef struct
{ RecType r[MAXSIZE+1]； //r[0]用作监视哨
int length； //实际表长 length≤MAXSIZE
}SeqList； //表和表长合并为 SeqList
或,//表和表长分别定义和说明
RecType r[MAXSIZE+1]； //r[0]用作监视哨
int length； //实际表长 length≤MAXSIZE
5.排序算法分析
(1)时间复杂度
● 对 n个记录排序，所需 比较关键字的次数 ；
最好情况；最坏情况；平均情况
● 对 n个记录排序，所需 移动记录的次数 ；
最好情况；最坏情况；平均情况
(2)空间复杂度排序过程中，除文件中的记录所占的空间外，
所需的 辅助存储空间 的大小。
6.内排序方法
(1)对顺序表的排序
● 插入排序：直接插入排序；
折半插入排序； 2-路插入排序；表插入排序；
希尔 (Shell)排序 ；
● 选择排序：简单选择 /选择排序；
树形选择排序；堆排序
● 归并排序
2-路归并排序
k-路归并排序
● 交换排序冒泡排序：单向冒泡排序，双向冒泡排序快速排序
● 基数排序多关键字排序最高位优先法最低位优先法链式基数排序
(2)对单链表的 排序直接插入,简单选择,冒泡排序,基数排序
10.2 插入排序算法基本思想将待排序的记录插入到已排序的子文件中去，使得插入之后得到的子文件仍然是有序子文件。插入一个记录，首先要对有序子文件进行查找，以确定这个记录的插入位置。按查找方式的不同，插入排序又可以分为线性插入排序和折半插入排序，前者使用顺序查找，后者使用折半查找。
1.直接插入排序 (线性插入排序 )
设待排序的文件为 (r[1],r[2],...,r[n])
关键字为 (r[1].key,r[2].key,...,r[n].key)
首先,将初始文件中的记录 r[1]看作有序子文件；
第 1遍：将 r[2]插入有序子文件中：若 r[2].key<r[1].key，
则 r[2]插在 r[1]之前；否则，插在 r[1]的后面。
第 2遍：将记录 r[3]插入前面已有 2个记录的有序子文件中，
得到 3个记录的有序子文件。
以此类推，依次插入 r[4],...,r[n],最后得到 n个记录的递增有序文件。
例,直接插入排序,设 K0为 "监视哨,
K0 K1 K2 K3 K4 K5 K6
初始关键字,( 43 ) 21 89 15 43 28
(43后移 ) ┌─┘
↓
第 1遍 (趟 )排序后,21 ( 21 43 ) 89 15 43 28
(不后移 ) │
↓
第 2遍排序后,89 ( 21 43 89 ) 15 43 28
(89,43,21后移 ) ┌──────┘
↓
第 3遍排序后,15 ( 15 21 43 89 ) 43 28
(89后移 ) ┌─┘
↓
第 4遍排序后,43 ( 15 21 43 43 89 ) 28
(89,43,43后移 ) ┌──────┘
↓
第 5遍排序后,28 ( 15 21 28 43 43 89)
直接插入排序算法
void InsertSort(RecType r[],int n）
// 对数组 r[1..n]中的 n个记录作插入排序
{ int i,j；
for (i=2； i<=n； i++)
{ r[0]=r[i]； //待插记录 r[i]存入监视哨中
j=i-1； //从 r[i-1]开始向左扫描
while(r[0].key<r[j].key)
{ r[j+1]=r[j]； //记录后移
j--； //继续向左扫描
}
r[j+1]=r[0]； //插入记录 r[0],即原 r[i]
}
}
直接插入排序算法分析：
(1)最好情况,原 n个记录递增有序：
比较关键字 n-1次移动记录 2(n-1)次
ri r1 r2 ……
…
ri-1 ri … rn
r[0] r[1] r[2] r[i-1] r[i] r[n]
(2)最坏情况,原 n个记录递减有序：
比较关键字的次数,
n
∑ i = 2+3+...+n =(n-1)(n+2)/2 = O(n2)
i=2
移动记录的次数 (个数 ):
n
∑ (i-1+2) = 3+4+...+(n+1)
i=2
=(n-1)(n+4)/2 次 = O(n2)
ri r1 r2 ……
…
ri-1 ri … rn
r[0] r[1] r[2] r[i-1] r[i] r[n]
ri r1’ r2 ’ ……
…
ri-1 ’ ri … rn
r[0] r[1] r[2] r[i-1] r[i] r[n]
(3)平均比较关键字的次数约 为,
n n i+1
∑ (1+2+… +i)/i= ∑ --- =(3+4+...+(n+1))/2
i=2 i=2 2
=(n-1)(n+4)/4=O(n2)
平均移动记录的次数约为,
n n (i+3)
∑ ((0+2)+(1+2)+… +(i-1+2))/i=∑ ----- =(5+6+...+(n+3))/2
i=2 i=2 2
=(n-1)(n+8)/2=O(n2)
故,时间复杂度为 O(n2)。
(4) 只需 少量中间变量 作为辅助空间。
(5) 算法是 稳定 的。
10.3 选择排序
1.简单 选择 (选择排序 )
算法基本思想设待排序的文件为 (r[1],r[2],...,r[n]),关键字为
(r[1].key,r[2].key,...,r[n].key),
第 1趟 (遍 )：在 (r[1],r[2],...,r[n])中,选出关键字最小的记录 r[min].key,若 min<>1,则交换 r[1]和 r[min]；
需要进行 n-1次比较。
第 2趟 (遍 )：在 n-1个记录 (r[2],...,r[n])中,选出关键字最小的记录 r[min].key,若 min<>2,则交换 r[2]和 r[min]；
需要进行 n-2次比较。
.....,
第 n-1趟 (遍 )：在最后的 2个记录记录 (r[n-1],r[n])中,选出关键字最小的记录 r[min].key,若 min<>n-1,则交换 r[n-1]
和 min]； 需要进行 1次比较。
例,
k1 k2 k3 k4 k5 k6
初始关键字,（ 43 89 21 43 28 15 ）
↑ ↑
第 1遍排序后,15 （ 89 21 43 28 43 ）
↑ ↑
第 2遍排序后,15 21 （ 89 43 28 43 ）
↑ ↑
第 3遍排序后,15 21 28 （ 43 89 43 ）
↑↑
第 4遍排序后,15 21 28 43 （ 89 43 ）
↑ ↑
第 5遍排序后,15 21 28 43 43 89
简单选择排序算法：
void SelectSort(RecType r[],int n)
// 对数组 r[1..n]中 的 n个记录 作简单选择 排序
{ int i,j,min;
RecType x; //交换记录的中间变量
for (i=1;i<n;i++) //共 n-1趟 (遍 )
{ min=i; //r[i]为 最小记录 r[min]
for (j=i+1;j<=n;j++)
if (r[j].key<r[min].key)
min=j; //修改 min
if (min!=i) //若 r[min]不是 r[i]
{ x=r[min]; //交换 r[min]和 r[i]
r[min]=r[i]; r[i]=x;
}
}
}
算法分析：
(1)比较次数,在任何情况下,均为
n-1
∑ (n－ i)＝ (n-1)+(n-2)+...+1i=1
＝ n(n-1)/2 ＝ O(n2)
(2)交换记录的次数在最好情况下,原 n个记录递增有序：
不移动记录 。
在最 坏 情况下,每次都要交换数据 （ 不是递减有序 ）
共交换记录 n-1对,移动记录数 3(n-1)次 。
故,时间复杂度为 O(n2)。
(3)只需 少量中间变量 作为辅助空间 。
(4)算法是 不稳定 的 。
2.堆排序（ Heap Sort)
堆的定义,n个元素的序列 {k1,k2,…,k n} 当且仅当满足下关系时，
称之为 堆 。
ki ≤ k2i ki ≥ k2i
或
ki ≤ k2i+1 ki ≥ k2i+1
(i=1,2,…,?n/2?)
其中,前面一种称为小顶堆；
后面一种称为大顶堆。
n个元素的序列 {k1,k2,…,k n}可看成是一个结点个数为 n
的完全二叉数，若其为大顶堆，则 k1最大；若其为小顶堆，
则 k1最小。
例,序列 1,{96,83,27,38,11,09}
序列 2,{12,36,24,85,47,30,53,91}
96
83 27
38 11 09
36
85 47
91
24
30 53
12
序列 2的二叉树 (小 顶 )堆序列 1的二叉树 (大顶堆 )
通常,n个元素的序列 {k1,k2,…,k n} 不符合堆的定义，
所以，面临的第一个问题：
问题 1：如何将序列 {k1,k2,…,k n} 处理成（大顶）堆（初始化）？
问题 1一旦解决，得到规模为 n的堆，则 k1最大，将 k1与
kn互换，则最大的数已放置到最后，同时，剩下的序列
{k1,k2,…,k n-1}不是堆，如何将其重新处理成规模为 n-1的堆，
求取第二大的数据，以此类推，堆的规模逐步减小，直到求出第 n-1大的数据，完成递增排序。所以，面临的第二个问题是：
问题 2：如何在堆顶元素被替换后，调整剩余元素成为一个新的堆。
提示,根据上述过程描述,借助大顶堆可实现序列的递增排序；
借助小顶堆可实现序列的递减排序。
96
8327
11 3825 22
09
问题 2方法,某序列的堆形式,{96,27,83,25,22,11,38,09}
09
8327
11 3825 22
96
09
83
27
11 3825 22
96
09
83
27
11
38
25 22
96
除顶以外，
其它都符合堆的定义
83=max(83,27)
38=max(38,11)
s
s
s
j
j
j?s
j?s
typedef SqList HeapType; //采用顺序表存储表示
void HeapAdjust(HeapType &H,int s,int m)
//已知 H.r[s…m] 中记录的关键字除 H.r[s].key之外均满足堆的定义，本函数调整 H.r[s]的关键字,使 H.r[s…m] 成大顶堆。
{ rc=H.r[s]; //空出 s的记录位置
for(j=2*s; j<=m;j*=2) { //j<=m表示 s有左孩子序号 j=2*s
if (j<m && H.r[j].key< H.r[j+1].key) //j<m表示 s有右孩子 j+1
j++; //计算 s的具有较大关键字的孩子的序号 j
if (rc.key> H.r[j].key) // rc在 s的结点时满足结点定义，调整完毕
break;
H.rs[s]=H.r[j];s=j; //s的较大孩子上移，修改 s下移
} //正常结束时,s的结点无孩子结点。
H.r[s]=rc; }
38
97
7649
65
13 98
49
问题 1方法,建立序列,{49,38,65,97,76,13,27,49}
的初始堆。
1。对以最后一个结点（序号 n）
的双亲结点（序号 i=?n/2?）
为根的二叉树，进行堆调整。
38
97 76
49
65
13 98
49
2。对以序号序号 i=i-1的结点为双亲结点为根的二叉树，进行堆调整。
38
97 76
49
6513
98
49
3。对以序号序号 i=i-1的结点为双亲结点为根的二叉树，进行堆调整。
97
38 76
49
6513
98
49
97
38
7649 6513
98
49
97
38
7649 6513
98
49
97
38
7649 6513
49
98
97
38
7649 4913
65
98
4。对以序号序号 i=i-1的结点为双亲结点为根的二叉树，进行堆调整。此时 i已等于 1，调整完后,初始大顶堆建成 。
97
98
7649 4913
65
38
76
3849 4913
65
97
98
76
3849 9713
65
49
98
49
3849 9713
65
76
98
选择较小范围选择 较小范围调整调整
i>0
真假堆排序结束H.r[1]H.r[i]
调整以 i为根的二叉树
i--
n/2i
n?i
i>1
真假
i--
调整剩余 i-1个结点的二叉树初始化堆选择、调整
n-1次算法分析与评价：
对深度为 k的堆，调整算法进行的关键字比较次数至多为
2(k-1)次，
建立 n个元素的初始堆，调用 HeapAdjust算法?n/2?次，总共进行的关键字比较次数不超过 4n次。
n个结点的完全二叉树深度为 h=?log2n?+1
需要调整的层为 h-1层至 1层,以第 i层某结点为根的 二叉树深度对应为 h-i+1,第 i层结点最多为 2i-1个，故调整时比较关键字最多为：
2i-1*2*(h-i+1-1)= 2i*(h-i)
令 j=h-i,当 i=h-1时 j=1 当 i=1时 j=h-1
2h-j*j=2h-1*1+ 2h-2*2+… + 21*(h-1)=2h+1-2h-2
< 2h+1 =2?log2n?+2<=4* 2 log2n =4n
1
1hi
1
1hi
1
1
h
j
算法分析与评价 (续）,
n个结点的完全二叉树深度为?log2n?+1,选择调整过程 n-1
次，总共比较次数 至多为：
2 （?log2(n-1)?+?log2(n-2)?+… +?log22?)<2n(?log2n?)
最坏情况下，算法的时间复杂度为 O(4n+nlogn)?O(nlogn) ；
仅需要 一个记录大小 供交换用的辅助存储空间；
堆排序是 不稳定排序 。
堆排序对记录较少的文件不提倡，对 较大的文件很有效 ；
家庭作业
1.假定不使用 监视哨,试重写对顺序表直接插入排序的算法。
2.设单链表的结点结构为 (data,next),data为整型，试用插入排序的思想方法，对以 head为头指针的不带表头结点的单链表排序，写出算法。
3.设单链表的结点结构为 (data,next),data为整型，试用选择排序的思想方法，对以 head为头指针的不带表头结点的单链表排序，写出算法。
40 9 ∧30121520head
30 40 ∧2015129head
