1
第十章排序
? 基本概念基本概念
? 插入排序插入排序
? 快速排序快速排序
? 选择排序选择排序
? 归并排序归并排序
? 基数排序基数排序
数
据
结
构
之
内
部
排
序
2
10. 1 概念
?排序
设含有 n个记录的文件 {R
1
,R
2
,...,R
n
}，
其相应的关键字为 {K
1
,K
2
,...,K
n
}，需确定
1,2, …, n的一种排列 p1,p2, …, pn,使其相应
的关键字满足如下的非递减 (或非递增 )关
系 K
p1
<=K
p2
<=…<=K
pn
, 从而使序列
{R
p1
,R
p2
,...,R
pn
}按关键字有序 , 该过程称为
排序 。
2
数
据
结
构
之
内
部
排
序
3
?排序的稳定性
对所有的 K
i
=K
j
(i≠ j), 若排序前 R
i
领先于
R
j
, 排序后 R
i
仍领先于 R
j
, 则称该排序方法是 稳
定的 ；反之，若可能使排序后的序列中 R
j
领先
于 R
i
, 则称所用的排序方法为 不稳定 的。
稳定性是对序列中的两个相同关键字的
记录在初始序列和最终有序序列中相对位置 (
即领先关系 )是否变化的描述。
数
据
结
构
之
内
部
排
序
4
?内部排序和外部排序
? 内部排序 ：待排序文件的全部记录存放在
内存进行的排序，称为 内部排序 。
? 外部排序 ：待排序记录的数量很大 , 以致
内存一次不能容纳全部记录 , 排序过程中
需要进行内外存数据交换的排序，称为 外
部排序 。
3
数
据
结
构
之
内
部
排
序
5
? 内排序分类
按排序过程依据的原则分为：插入排序
交换排序
选择排序
归并排序
计数排序
按排序过程所需的工作量分：简单排序 O(n
2
)
先进排序 O(nlog n)
基数排序 O(d． n)
数
据
结
构
之
内
部
排
序
6
? 存储形式
? 连续存放在地址连续的一组存储单元上。
? 静态链表存储形式。
待排记录存放在一组地址连续的存储单
元中，同时另设一个指示 各个记录存储位置
的地址向量，在排序过程中不移动记录本身，
只修改这些记录的地址，在排序结束之后在
按照地址向量中的值调整记录的存储位置。
4
数
据
结
构
之
内
部
排
序
7
?排序算法的性能度量
? 排序算法的时间复杂度：
记录移动次数、比较次数；
? 空间复杂度；
? 排序方法的稳定性
数
据
结
构
之
内
部
排
序
8
#define MAXSIZE 100 //顺序表的长度
Typedef int KeyType; //关键字类型为整数
类型
Typedef struct{ KeyType key; //关键字项
InfoType otherinfo; //其它数据项
}RedType; //记录类型
type struct { RedType r[MAXSIZE+1];
//r[0]空作为哨兵
int length; //顺序表长度
}SqList; //顺序表类型
5
数
据
结
构
之
内
部
排
序
9
10. 2 插入排序
?直接插入排序：
? 基本操作：是将一个记录插入到已排
好序的有序表中，从而得到一个新的
记录数增 1的有序表。
? 整个排序过程：先将原序列中的第一
个记录看成是一个有序的子序列，然
后，从第 2个记录起逐个进行插入，直
至整个序列变成按关键字非递减有序
序列为止。
数
据
结
构
之
内
部
排
序
10
例：已知关键字为{ 49 38 65 97 76 13 27
49}，采用直接插入排序方法对其进行排序。
初始关键字： （ 49） 38 65 97 76 13 27 49
i=2: (38) (38 49) 65 97 76 13 27 49
i=3: (65) (38 49 65) 97 76 13 27 49
i=4: (97) (38 49 65 97) 76 13 27 49
i=5: (76) (38 49 65 76 97) 13 27 49
i=6: (13) (13 38 49 65 76 97) 27 49
i=7: (27) (13 27 38 49 65 76 97) 49
i=8: (49) (13 27 38 49 49 65 76 97)
6
数
据
结
构
之
内
部
排
序
11
void InsertSort(SqList &L){
for(i=2; i<=L.length;++i)
if(L. r[i]. key<L.r[i-1]. key){
L.r[0]=L. r[i]; //复制哨兵 //
for(j=i-1;L. r[0]. key<L. r[j]. key;--j)
L. r[j+1]=L. r[ j ];
L. r[j+1]=L. r[ 0 ];
}
} //O( n*n )
性能分析：（ 1）时间复杂度： O(n*n)
（ 2） 空间复杂度： O(1)
（ 3）排序方法是稳定的
数
据
结
构
之
内
部
排
序
12
? 算法分析算法分析
?空间上 ，只需 i， j两个整型变量和一个记录的
辅助空间 r[0], r[0]作为 “监视哨 ”，控制待插入
元素相对于有序子文件为最小时 WHILE循环
的结束，同时也用于 暂存 待插入元素。
?时间上 ，只包含比较关键字和移动记录两种
操作。
?当待排序初始文件按关键字非递减有序 (正序 )时：
?对每个记录只进行一次比较，整个排序过程共
n
进行了∑进行了∑ 1=n-1次比较次比较 (最少最少 )；；
i=2
? 每个记录都要进行 r[i]移到 r[0]和 r[0]移到 r[j+1]两
次移动，因此共移动 2(n-1)次 (最少 )。
7
数
据
结
构
之
内
部
排
序
13
?当待排序文件按关键字非递增有序 (逆序 )
时
?记录 r[i](i=2,3,...n)均要和前 i-1个记录及 r[0]进
行比较，整个排序过程共进行了
n
∑ i=(n+2)(n-1)/2次比较 (最多 )；
i=2
?移动记录次数：每个记录都要进行 r[i]移动到
r[0]和 r[0]移动到 r[j+1]两次移动，另外当
r[i].key＜ r[j].key时，还将 r[j]移动到 r[j+1]，
所以，当初始文件为逆序时移动记录次数最
多 , 为
n
∑ (i-1)+2(n-1)=(n+4)(n-1)/2次 (最多 )。
数
据
结
构
之
内
部
排
序
14
?结论结论
?直接插入排序的效率与待排文件的关
键字排列有关；
?直接插入排序的时间复杂度为 O(n
2
)；
?直接插入排序是稳定的 (这一点由过程
中 WHILE语句的条件 “＜ ”保证的 )。
8
数
据
结
构
之
内
部
排
序
15
? 折半插入排序
Void BInsertSort ( Sqlist &L) {
for ( i=2; i<=L.length; ++i ) {
L.r[0]=L.r[i];
low=1; high=i-1;
while ( low<=high) { //折半查找位置
m=(low+high)/2;
if ( 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];
} }
数
据
结
构
之
内
部
排
序
16
? 2-路插入排序
例： 对初始关键字为{49，38，65，97，76，13，27，
49} 的序列进行2-路插入排序。
解：其2路插入排序的过程如下
初始关键字： 49 38 65 97 76 13 27 49
i=1: (49)
first↑↑final
i=2: (49) (38)
↑final ↑first
i=3: (49 65) (38)
↑final ↑first
9
数
据
结
构
之
内
部
排
序
17
i=4: (49 65 97) (38)
↑final ↑first
i=5: (49 65 76 97) (38)
↑final ↑first
i=6: (49 65 76 97) (13 38)
↑final ↑first
i=7: (49 65 76 97) (13 27 38)
↑final ↑first
i=8: (49 49 65 76 97 13 27 38)
↑final ↑first
数
据
结
构
之
内
部
排
序
18
与折半插入排序相比， 2路插入排序可以减
少记录移动的次数，但不能避免记录的移动。
此外需要 N个额外的存储空间。并且如果 L.r[1]
是待排序记录中关键字最小（或最大）的记录
时， 2路排序就没有优越性可言了。
10
数
据
结
构
之
内
部
排
序
19
? 表插入排序
如果希望在排序过程中不移动记录，只有改变存储结构，进行表插
入排序。表插入排序的存储结构用 C语言表述如下：
#define SIZE 100 //静态连表容量
typedef struct{
RcdType rc; //记录项
int next; //指针项
}SLNode; //表结点类型
typedef struct{
SLNode r[SIZE]; //0号单元为表头结点
int length; //链表当前长度
}SLinkListType; //静态链表类型
数
据
结
构
之
内
部
排
序
20
其实现方法：
首先将静态链表中数组下标为 “1”的分量（结点）和表
头结点构成一个循环链表（表头接点记录的关键字取最
大的整数 MAXINT），然后依次将下标为 “2”至 “n”的
分量（结点）按记录关键字非递减有序插入到循环链表
中。
例：采用表插入排序将下面的序列{49，38，65，
97，76，13，27，49}按从小到大的顺序排列。
11
数
据
结
构
之
内
部
排
序
21
解：其插入过程可按下面的步骤进行
0 1 2 3 4 5 6 7 8
27
0
49 38 65 76 13 49
1
97MAXINT
初始
状态
27
0
49
1
38 65 76 13 49
2
97MAXINT
i=2
27
3
49
1
38
0
65 76 13 49
2
97MAXINT
i=3
27
3
49
1
38
4
65 76 13 49
02
97MAXINT
i=4
数
据
结
构
之
内
部
排
序
22
27
3
49
1
38
5
65
4
76 13 49
02
97MAXINT
i=5
27
3
49
1
38
5
65
4
76
2
13 49
06
97MAXINT
i=6
2
27
3
49
1
38
5
65
4
76
7
13 49
06
97MAXINT
i=7
2
27
8
49
1
38
5
65
4
76
7
13
3
49
06
97MAXINT
i=8
0 1 2 3 4 5 6 7 8
12
数
据
结
构
之
内
部
排
序
23
表插入排序的基本操作仍是将一个记录插
入到已排好序的有序表中。和直接插入排序相
比，是以修改 2n次指针值代替移动记录，排序
过程中所需进行的关键字之间的比较次数相同。
其时间复杂度认为 O（ n
2
）。
上面的排序后形成的表只能进行顺序查找，
如果希望对该表进行随机查找，如折半查找，
就需要对该表的记录进行重新排序。
数
据
结
构
之
内
部
排
序
24
? 希尔排序
? 基本思想：先将整个待排记录序列 分割 成为若
干子序列分别进行直接插入排序，待整个序列
中的记录“基本有序”时，再对全体记录进行
一次直接插入排序。
? 希尔排序的特点：子序列的构成不是简单的
“逐段分割”，而是，将 ( 位置 ) 相隔某个“增
量”的记录组成一个子序列。
? 增量序列的选择：
希尔取法： d[0]=? n / 2? d[1]=? d[0] / 2?......
d[i+1]= ?d[i] / 2? ... 最后一个增量必须等于 1
每一个增量对应一趟希尔排序
13
数
据
结
构
之
内
部
排
序
25
04554927137697653849
初始关键字
13
49
27 38
49 65
55 97
04 76
76976538490455492713
一趟排
序结果
76976538490455492713
13 38 55 76
04 27 65
49 49 97
76976555492738490413
二趟排
序结果
97766555494938271304
三趟排
序结果
数
据
结
构
之
内
部
排
序
26
原始序列：
d0 =5, 分割成 5 组
一趟希尔
排序结果
d1 =2, 分割成 2 组
二趟希尔
排序结果
d2 =1, 对全体记录进行一次直接插入排序
三趟希尔
排序结果
顺序存储
原始序列
14
数
据
结
构
之
内
部
排
序
27
Shell算法描述
void ShellSort(SqList &L){
for(d=L.length /2 ; d>=1 ; d=d/2)
for(i=d+1; i<=L.length;i++) //完成一趟 Shell 排序
if(L.r[i].key<L.r[i-d].key){// 寻找插入位置
L.r[0]=L.r[i]; //暂存
for(j=i-d ; j>0&&L.r[0].key<L.r[j].key ; j-=d)
L.r[ j+d ]=L.r[ j ]; //数据向后搬移
L.r[ j+d ]=L.r[0]; //插入
} } //ShellSort end
性能分析： 时间复杂度： O(n )；空间复杂度： O(1)；
Shell 排序方法不稳定；
3/2
数
据
结
构
之
内
部
排
序
28
一趟 Shell排序算法的另一种描述
void ShellInsert(SqList &L , int d){
for(k=1 ; k<=d ; k++) //O(d), d组子序列分别排序
for(i=d+k ; i<=L.length ; i+=d){ //O( n / d )
e=L.r[i] ;
for(j=i-d ; j>0 && e. key<L.r[j].key ; j-=d)
L.r[ j+d ]=L.r[ j ]; //O(n/d)//
L.r[j+d]=e ;
} }// O(n*n/d)
void ShellSort(SqList &L , int dlta[] , int t ){
for(k=0; k<t; k++) ShellInsert(L,dlta[k]);
}// O(log n)
15
数
据
结
构
之
内
部
排
序
29
10. 3 交换排序 ——快速排序
? 基本思想：是通过一趟排序将一个记录
（其关键字叫做控制关键字） 置于排序序
列的 最终 位置上，从而将文件分成两部分，
使关键字值比控制关键字小的都在前面部
分，大的均在其后。然后 再对这两部分重
复上述过程进行排序 ，直至每一部分中只
剩下一个记录为止。
一般，选择待排序列中最左端的关键
字作为控制关键字。
数
据
结
构
之
内
部
排
序
30
4965977649133827
4965977649133827
4965497697133827
4965137697493827
9776654949382713
6549
9776654949382713
high ↑↑Low ←↑high
↑ Low →↑Low ↑ high
↑ Low ↑ high ←↑high
Pivtkey
4949137697653827
↑ Low →↑Low ↑ high
↑Low ←↑high
4927137697653849
一趟
结果
二趟
排序
16
数
据
结
构
之
内
部
排
序
31
一趟快速排序算法描述
int QuickOne(SqList &L, int i , int j ){
L.r[0]=L.r[i]; e=L.r[i].key; //e 是控制关键字
while(i<j){ //i=j时，找到 e 的最终位置
while(e <=L.r[j].key && i<j) j--;//与后比较
L.r[i]=L.r[j];
while(e >=L.r[i].key && i<j) i++;//与前比较
L.r[j]=L.r[i];
}//while
L.r[i]=L.r[0];
return i;
}//end
数
据
结
构
之
内
部
排
序
32
快速排序的非递归算法描述
void QuickSort(SqList &L){
InitStack(S); //建立 int 型动态栈作为辅存
push(S,1); push(S , L.length);
while(! Empty(S)){
pop(S,end) ; pop(S, start);
i=QuickOne(L , start , end );
//如果左右两边各有 2个以上关键字，首、尾入栈
if( start <i-1 ) {push(S, start);push(S, i-1);}
if(end>i+1) {push(S,i+1);push(S,end) ; }
}
}
17
数
据
结
构
之
内
部
排
序
33
? 快速算法的性能
? 平均时间性能： O(n*log n)， 最坏为 O(n*n)
? 空间复杂度：
最坏情况，栈的最大深度 n
最好情况，栈的最大深度 ?log n ? + 1
通过改进算法可以改善空间复杂度：在一趟
排序之后比较分割所得两部分的长度，且先对长
度短的子序列中的记录进行快速排序，则栈的最
大深度可降为 O( log n)
? 快速排序方法是不稳定的。
数
据
结
构
之
内
部
排
序
34
用队列实现快排的非递归算法
QuickSort_Q(SqList &L){
// 建立一个足够大的循环队列 //
InitQ(Q) ; InQ(Q , 1) ; InQ(Q , L.length);
while(!empty(Q)){
OutQ(Q , start); OutQ(Q , end );
i=QuickOne(L ,start , end );
if(start<i-1)
{ InQ(Q , start); InQ(Q , i-1 );}
if(end >i+1)
{ InQ(Q , i+1) ; InQ(Q , end );}
} }
18
数
据
结
构
之
内
部
排
序
35
10. 4 选择排序
? 简单选择排序
第一趟选择排序的操作为：通过 n-1次关键
字之间的比较，从 n 个记录中选择出关键字最小
的记录，并和第 1 个记录交换之。
总共需要 n-1趟选择排序。
void SelectSort(SqList &L){
for(i=1 ; i<L.length ; i++){
for(k=i , j=i ; k<=L.length ; k++)
if(L.r[j].key > L.r[k].key) j=k;
if (i!=j) L.r[i] L.r[ j] ; }
}//O( n*n )
数
据
结
构
之
内
部
排
序
36
?堆排序
堆的定义： n个元素的序列 { k1 , k2 , ... , kn }，
当且仅当满足下列关系时，称为堆。
大顶堆： ki≥ k2i , k2i+1
小顶堆： ki≤ k2i , k2i+1
19
数
据
结
构
之
内
部
排
序
37
调整无序序列为大顶堆；
for(i=L.len;i>1;i--){
L.r[1]?L.r[i]；
将 L.r[1..i-1]重新调整为大
顶堆； }
大顶堆排序结果为正序序列
小顶堆
数
据
结
构
之
内
部
排
序
38
堆排序的过程
20
数
据
结
构
之
内
部
排
序
39
49
38 65
97
76
13 27
49
49
38 65
97
76
13 27
49
49
38 65
49
76
13 27
97
49
38 13
97
76
65 27
49
堆的创建过程
数
据
结
构
之
内
部
排
序
40
13
38 49
97
76
65 27
49
13
38 27
97
76
65 49
49
21
数
据
结
构
之
内
部
排
序
41
调
整
以
s
为
根
结
点
的
树
为
堆
HeapCreate( SqList &L , int s , int len ){
e=L.r[s];
for(j=2*s ;j<=len ; j*=2){
if(j<len && L.r[j].key<L.r[j+1].key) j++;
if(e.key>=L.r[j].key) break;//无须调整
/* 大的数据往上提， s 往下移 ，继续调整 */
L.r[s]=L.r[j] ; s =j ;}
L.r[s]=e ;
}
s =1
S的左右子树必须均为堆
才可以调整
数
据
结
构
之
内
部
排
序
42
堆
排
序
算
法
描
述
HeapSort(SqList &L){
for( i=L.length/2 ; i>0 ; i--)
HeapCreate( L , i , L.length );
for( i=L.length ; i>1 ; i-- ) {
L.r[1] ?L.r[i];
HeapCreate(L , 1 , i-1);
} }
22
数
据
结
构
之
内
部
排
序
43
堆排序的性能
1.堆排序对n较大的文件很有效；
2.运行时间主要耗费在建初始堆和调整建
新堆时进行的反复“筛选”上，堆排序
在最坏的情况下，其时间复杂度为
O(n*log n)
3.空间复杂度： O(1)
4.堆排序方法不稳定。
数
据
结
构
之
内
部
排
序
44
10. 5 归并排序
? “归并”的含义是将两个或两个以上的有序表
组合成一个新的有序表。
? 2-路归并排序的排序方法：
假设初始序列含 n 个记录，则可看成是 n
个有序的子序列，每个子序列的长度为 1，然
后（ 相邻的 ）两两归并，得到 ?n / 2?个长度为
2或 1的有序子序列；再（ 相邻的 ）两两归
并， ……，如此重复，直到得到一个长度为
n的有序序列为止。
23
数
据
结
构
之
内
部
排
序
45
27137697653849
2713 7665 9738 49
13 27 7638 49 65 97
13 27 38 49 65 76 97
一趟归并
二趟归并
三趟归并
数
据
结
构
之
内
部
排
序
46
? 两两归并的算法描述
Merge( int a[ ], int b[ ] , int i , int n , int m){
for(j=n+1 , k=i ; i<=n && j<=m ; k++){
if(a[i]<=a[j]) b[k]=a[i++];
else b[k]=a[j++];
}
if(i<=n) for( ; i<=n;i++,k++) b[k]=a[i];
if(j<=m) for( ; j<=m ; j++,k++) b[k]=a[j];
}//O(两个归并段长度之和 )
24
数
据
结
构
之
内
部
排
序
47
归
并
排
序
的
非
递
归
算
法
描
述
typedef struct {int *elem; int len;}SqList;
void MergeSort( SqList &L){ h=1; //h是归并段长
B=(int*)malloc(L.len*sizeof(int));
while( h <(L.len)){i=0;
while((i+h)<(L.len)){ //一趟归并排序
if((i+2*h)<(L.len)) m=i+2*h-1;
else m=(L.len)-1 ;
Merge(L.elem , B , i , i+h-1 , m);//O(2*h)
i=i+2*h;} //O( L.len/(2*h) )
for(i=0;i<=m;i++) L.elem[i]=B[ i ];
h=2*h; } //O(log n) (n=L.len)
free( B ); }//O(n*log n )
数
据
结
构
之
内
部
排
序
48
? 归并排序性能分析归并排序性能分析
? 时间复杂度 : O( n * log n) 分析如下 :
两两归并排序 : 2*h
一趟归并排序 :调用 Merge算法 ?n/2h?次
整个归并排序需进行 log n 趟
? 空间复杂度 : O(n)
? 归并排序方法是稳定的。
25
数
据
结
构
之
内
部
排
序
49
? 基数排序
基数排序是一种借助 多关键字排序 的思想，对 单逻辑关键字 进行
排序的方法。
如果关键字是数值，则可把每个十进制数看成一个关键字，若所
有关键字 0≤k ≤ 999，可按三个关键字位 k
1
， k
2
， k
3
，其中 k
1
为百位数，
k
2
为十位数， k
3
为个位数，且 0 ≤ k
i
≤ 9 ( i=1， 2， 3 )，称 10为基，按
LSD（最低位优先）方式，从最低位起，按关键字值不同将文件记录
分配到堆中再收集之，如此重复三次，便是 基数排序 。
10. 6 基数排序
数
据
结
构
之
内
部
排
序
50
尾指针 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
例：采用链式基数排序将序列{278，109，063，930，589，
184，505，269，008，083}按从小到大的顺序排列。
109 083278 063 930 589 184 505 269 008
第 1趟收集之后
063 269930 083 184 505 278 008 109 589
269
930
589008083
184 109278063 505
头指针 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
第
一
趟
分
配
26
数
据
结
构
之
内
部
排
序
51
尾指针 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
第 2趟收集之后
008 589505 109 930 063 269 278 083 184
269
930
589
008
083
184
109
278063505
头指针 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
第
二
趟
分
配
063 269930 083 184 505 278 008 109 589
数
据
结
构
之
内
部
排
序
52
尾指针 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
第 3趟收集之后
063 930008 083 109 184 269 278 505 589
269 930
589
008
083
184
109
278
063
505
头指针 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
第
三
趟
分
配
其相应的程序实现请参照教材 287~289页，在此不做详细介绍。
008 589505 109 930 063 269 278 083 184
27
数
据
结
构
之
内
部
排
序
53
链式基数排序的性能分析：
对于 n个记录（假设每个记录含有 d个关键字，每个关键字的取值
范围为 rd个值）进行链式基数排序的时间复杂度为 O（ d（ n+rd）） ，
其中每一趟分配的时间复杂度为 O（ n） ，每一趟收集的时间复杂度
为 O（ rd） ，这个排序需进行 d趟分配和收集。
该排序需要的辅助存储空间为 2rd个队列指针。如果采用链表作为
存储结构，则相对与其他以顺序表结构存储记录的排序方法而言，还
增加 n个指针域的空间。
数
据
结
构
之
内
部
排
序
54
?各种内部排序方法比较如下：
O(rd)O(d(n+rd))O(d(n+rd))基数排序
O(n)O(nlog
n
)O(nlog
n
)归并排序
O(1)O(nlog
n
)O(nlog
n
)堆排序
O(log
n
)O(n
2
)O(nlog
n
)快速排序
O(1)O(n
2
)O(n
2
)简单排序
辅助存储最坏情况平均时间排序方法
从上表可得到下面的结论：
10. 6 各种内部排序方法的比较
28
数
据
结
构
之
内
部
排
序
55
结论
1、 从平均时间 看，快速排序最佳，所需时间最省，但快速排
序在最坏情况下的时间性能不如堆排序和归并排序。而后两者
相比较，在 n 较大时，归并排序所需时间较堆排序省。
2、 简单排序中，直接插入最简单，当序列基本有序或 n较小，
其最佳。
3 、 基数排序的时间复杂度可写成 O(d*n)，它最适用于 n值很
大而关键字较小的序列。
4、 从稳定性 来比较，基数排序是稳定的，所有时间复杂度为
O(n
2
)的简单排序也是稳定的，而快速排序、堆排序和希尔排序
等时间性能较好的排序方法是不稳定的。
数
据
结
构
之
内
部
排
序
56
本章重点
?各种排序方法以及程序实现。
?各种排序方法的中间执行过程。
?各种排序方法的性能比较。
29
数
据
结
构
之
内
部
排
序
57
排序作业
1.设有 1000个无序的元素，希望用最快的速度挑出
其中前 10个最大的元素，采用哪一种排序方法最
好？为什么？
2.给出一组待排序的记录，其关键字为： 12， 2， 16，
30， 8， 28， 4， 10， 20， 6， 18。写出用下列方
法进行排序时，每一趟排序结束时的状态。（ 1）
快速排序，（ 2）希尔排序，（ 3）堆排序，（ 4）
归并排序，（ 5）基数排序。
3.设计一个用链表表示的直接选择排序的程序。
*4.试构造一种排序方法，使五个整数至多用七次比
较就完成排序任务。
数
据
结
构
之
内
部
排
序
58
五个整数至多用七次比较
假设五个整数为： R1， R2， R3， R4， R5
算法步骤： *******归并插入排序法 *******
1. 两两归并：（ R1， R2），（ R3， R4）， R5 2次
2. 在 R1、 R3中取最小值： R3 1次
3. 组成有序段：（ R3， R1， R2）， R4， R5
4. 将 R5插入有序段（ R3， R1， R2） 2次
形成有序段（ R3， R5， R1， R2）
5. 将 R4 插入 R3 之后的有序段 2次
*****五个整数至多用七次比较就完成排序任务 *****
