第十章 内部排序
? 10.1 概述
? 10.2 插入排序
? 10.2.1 直接插入排序
? 10.2.3 shell排序
? 10.3 交换排序（快速排序）
? 10.4 选择排序
? 10.4.1 简单选择排序
? 10.4.3 堆排序
? 10.5 归并排序
? 10.6 基数排序
? 10.7 各种排序方法的比较讨论
10.1 内部排序 概述
?排序 (Sorting):
? 将数据元素 (或记录 )的一个任意序列,重新排列成
一个按关键字有序的序列。
? 排序方法的稳定性：
? 对关键字相同的数据元素，排序前后它们的领先关
系保持不变，则称该排序方法是稳定的。反之，称
该排序方法是不稳定的。
? 内部排序
? 待排序记录存放在计算机的内存中进行排序。
? 外部排序
? 待排序记录的数量很大，以致内存一次不能容纳全
部记录，在排序过程中尚需对外存进行访问的排序。
排序的分类
? 按排序过程依据的不同原则进行分类：
? 插入排序、
? 交换排序、
? 选择排序、
? 归并排序和
? 基数排序
? 按工作量分类，可以分为三类：
? (1)简单的排序方法,其时间复杂度为 O(n2);
? (2)先进的排序方法,其时间复杂度为 O(nlog2n);
? (3)基数排序，其时间复杂度为 O(dn);
排序的基本操作和
记录的存储方式
? 排序过程中需要的两种基本操作：
? （ 1）比较关键字的大小；
? （ 2）将记录从一个位置移至另一个位置。
? 待排序记录序列可有下列三种存储方式：
? （ 1）记录存放在一组连续的存储单元中；类似于线性表
的顺序存储结构，记录次序由存储位置决定，实现排序需
移动记录。
? （ 2）记录存放在静态链表中；记录次序由指针指示，实
现排序不需移动记录，仅需修改指针。 ---链排序
? （ 3）记录本身存放在一组连续的存储单元中，同时另设
指示各个记录存储位置的地址向量，排序过程中不移动记
录本身，而移动地址向量中相应记录的地址。排序结束后
再根据地址调整记录的存储位置 。 ---地址排序
待排序记录的数据类型
?#define MAXSIZE 20
?typedef int KeyType;
?typedef struct{
? KeyType key;
? InfoType otherinfo;
?}RcdType;
?typedef struct{
? RedType r[MAXSIZE+1];
? int length;
?}SqList;
10.2 插入排序
10.2.1 直接插入排序
? 例：序列为 {49,38,65,97,76,13,27,49}
? {(49),38,65,97,76,13,27,49}
? (38) {(38,49),65,97,76,13,27,49}
? (65) {(38,49,65),97,76,13,27,49}
? (97) {(38,49,65,97),76,13,27,49}
? (76) {(38,49,65,76,97),13,27,49}
? (13) {(13,38,49,65,76,97),27,49}
? (27) {(13,27,38,49,65,76,97),49}
? (49) {(13,27,38,49,49,65,76,97)}
直接插入排序算法
void InsertSort(SqList &L)
{ for(i=2; i<=L.length; ++i)
if ( LT(L.r[i].key,L.r[i-1].key) ){
L.r[0] = L.r[i]; // 复制为哨兵
for(j=i-1; LT(L.r[0].key,L.r[j].key); --j)
L.r[j+1] = L.r[j]; // 记录后移
L.r[j+1] = L.r[0];
}} // InsertSort
时间：最坏情形判断与移动各接近 n(n+1)/2;
最好情形判断 n次，无移动；故时间复杂度,O(n2)
空间：一个辅助空间
10.2.2 Shell排序算法
?基本思想：
? 先将整个待排序记录序列分割成若干
子序列分别进行直接插入排序，待整个
序列“基本有序”时，再对全体记录进
行一次直接插入排序。
?算法复杂度,O(n3/2)
Shell排序举例 （非稳定的）
二趟结果 {13,04,49,38,27,49,55,65,97,76}
增量取 1,13,04,49,38,27,49,55,65,97,76
三趟结果 {04,13,27,38,49,49,55,65,76,97}
一趟结果 {13,27,49,55,04,49,38,65,97,76}
增量取 3,13 55 38 76
27 04 65
49 49 97
例,{49,38,65,97,76,13,27,49,55,04}
增量取 5,49 13
38 27
65 49
97 55
76 04
10.3 交换排序
1,冒泡排序（ 其时间复杂度 O(n2)）
初
始
关
键
字
第
一
趟
排
序后
第
二
趟
排
序后
第
三
趟
排
序后
第
四
趟
排
序后
第
五
趟
排
序后
第
六
趟
排
序后
例,49 38 38 38 38 13 13
38 49 49 49 13 27 27
65 65 65 13 27 38 38
97 76 13 27 49 49
76 13 27 49 49
13 27 49 65
27 49 76
49 97
2,快速排序
----- 对冒泡排序的一种改进
?基本思想：
? 通过一趟排序将待排序记录分割成独
立的两部分，其中一部分的关键字均比
另一部分的关键字小，则可分别对这两
部分记录继续分别进行排序，以达到整
个序列有序。
快速排序举例
初始关键字,{49,38,65,97,76,13,27,49}
pivot key 49
jji
1次交换后,{27,38,65,97,76,13，, 49}
i ji
2次交换后,{27,38，, 97,76,13,65,49}
i jj
3次交换后,{27,38,13,97,76，, 65,49}
i ji
4次交换后,{27,38,13，, 76,97,65,49}
ji j
一趟完成后,{27,38,13,49,76,97,65,49}
快速排序分析
? 快速排序的平均时间为 T(n) = knlog(n)
?k为某个常数因子
? 经验表明,在同数量级的排序方法中,快速排序
的常数因子 k最小,
? 就平均时间而言,快速排序是最好的,
? 若初始序列按关键字基本有序,快速排序蜕化
为起泡排序,其时间复杂度为 O(n2)。
? 改进的方法，用“三者取中”的法则选取枢轴
记录（ pivotkey).
快速排序举例
初始关键字,{49,38,65,97,76,13,27,49}
pivot key 49
jji
1次交换后,{27,38,65,97,76,13，, 49}
i ji
2次交换后,{27,38，, 97,76,13,65,49}
i jj
3次交换后,{27,38,13,97,76，, 65,49}
i ji
4次交换后,{27,38,13，, 76,97,65,49}
ji j
一趟完成后,{27,38,13,49,76,97,65,49}
快速排序算法（一）
int Partition(SqList &L,int low,int high)
{L.r[0] = L.r[low]; // 用子表的第一记录作枢轴记录
pivotkey = L.r[low].key;
while(low<high){
while(low<high && L.r[high].key>=pivotkey) --high;
L.r[low] = L.r[high]; // 将比 pivotkey 小的记录移到低端
while(low<high && L.r[low].key<=pivotkey) ++low;
L.r[high] = L.r[low]; // 将比 pivotkey 大的记录移到高端
}
L.r[low] = l.r[0];
return low;
}
快速排序算法（二）
void Qsort(SqList &L,int low,int high)
{ if(low<high){
pivotloc = Partition(L,low,high);
Qsort(L,low,pivotloc-1);
Qsort(L,pivotloc+1,high);
}
} // QSort
void QuickSort(SqList &L){
Qsort(L,1,L.length);
} // QuickSort
10.4 选择排序
10.4.1,简单选择排序 （ 其时间复杂度 O(n2)）
? 基本思想：
? 每一趟在序列的后 n-i+1(i=1,2,...,n-1)个记
录中选取关键字最小的记录作为第 i个记录。
void SelectSort(SqList &L)
{ for(i=1; i<L.length; ++i){
j = SelectMinKey(L,i); // 在 L.r[i..length]中选择 key最小
if(i != j) L.r[i] <--> L.r[j]; // 与第 i个记录交换
}
} // SelectSort
初始关键字,{49,38,65,97,76,13,27,49}
第一次交换,{13,38,65,97,76,49,27,49}
i j
10.4.3 堆排序
? 堆的定义：
?n个元素的序列 {k1,k2,...,kn}当且仅当满足下
列条件时，称之为堆。
ki <= k2i ki >= k2i
ki <= k2i+1 ki >= k2i+1或 ( i = 1,2,...,[n/2] )
堆举例：
{96,83,27,38,11,09)
{12,36,24,85,47,30,53,91}
96
83
38 11 09
27
12
36
85 47 30
24
53
91
完全二叉树,且所有非叶
结点的值均不大于 (不小
于 )其左、右孩子结点的值
实现堆要解决的问题
? （ 1）如何从一个无序序列建成一个堆？
? （ 2）如何在输出堆顶元素之后，调整剩余元
素成为一个新的堆？
12
36
85 47 30
24
53
91 (a)
91
36
85 47 30
24
53
12 (b)
91
36
85 47 30
24
53
(c)
24
36
85 47 91
30
53
(d)
无序序列建成一个堆 （从第 n/2到 1个元素）
{49,38,65,97,76,13,27,49}
49
38
49 76 13
65
27
97 (b)
49
38
49 76 65
13
27
97 (c)
49
38
97 76 13 27
49 (a)
65
49
38
49 76 65
13
27
97 (d)
13
38
49 76 65
27
49
97 (e)
10.5 归并排序 (Merging Sort)
? 将两个或两个以上的有序表组合成一个新的有序表
? 2-路归并举例,
初始关键字, [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]
2-路归并算法
? void Merge(RcdType SR[],RcdType &TR[],int i,int m,int n)
? { // 将有序的 SR[i..m]和 SR[m+1..n]合并为有序的 TR[i..n]
? for(j=m+1,k=i; i<=m&&j<=n; ++k)
? { if LQ(SR[i].key,SR[j].key) TR[k] = SR[i++];
? else TR[k] = SR[j++];
? }
? if(i<=m) TR[k..n] = SR[i..m]; //复制剩余的 SR[i..m]
? if(j<=n) TR[k..n] = SR[j..n]; //复制剩余的 SR[j..n]
? } // Merge
归并算法的特点
? 需要辅助空间, O(n)
? 整个归并需要 [log2n] 趟
? 时间复杂度, O(n log2n)
? 它是稳定的排序方法
? 思想可以推广到, 多 -路归并,
10.6 基数排序 (Radix Sorting)
? 不需要进行关键字之间的比较
? 借助多关键字排序的思想对单关键字排序
? 10.6.1 多关键字排序
? ?2<?3<?4<?5<?6<?7<?8<?9<?10<?J<?Q<?K<?A<
? ?2<?3<?4<?5<?6<?7<?8<?9<?10<?J<?Q<?K<?A<
? ?2<?3<?4<?5<?6<?7<?8<?9<?10<?J<?Q<?K<?A<
? ?2<?3<?4<?5<?6<?7<?8<?9<?10<?J<?Q<?K<?A
? 花色 (?<?<?<?)优先于面值 (2<3<...<A)
? 最高位优先 (MSD),分成子序列分别排序
? 最高位优先 (LSD),通过若干次, 分配, 和, 收集,
10.6.2 基数排序
?借助,分配”和“收集“两种操作对单关
键字进行排序 。 例如,
? 278->109->063->930->589->184->505->269->008->083
0 1 32 4 5 6 7 8 9
278 109063930 184 505
589
269
008083
930->063->083->184->505->278->008->109->589->269
930->063->083->184->505->278->008->109->589->269
0 1 32 4 5 6 7 8 9
278
109
063930
184
505
589
269008
184
505->008->109->930->063->269->278->083->184->589
0 1 32 4 5 6 7 8 9
505008 109 930
063
269
278
083
083
589
008->063->083->109->184->269->278->505->589->930
基数排序分析 (d个关键字的取值范围 rd）
?“收集”重复的次数为 d;
?一轮“分配”的次数为 n+rd;
?时间复杂度为 O(d(n+rd));
?链式基数排序所需辅助存储量为 O(n)。
10.7 各种排序方法的比较讨论
排序方法
简单排序
Shell排序
快速排序
堆排序
归并排序
基数排序
平均时间
O(n2)
O(n3/2)
O(nlogn)
O(nlogn)
O(nlogn)
O(d(n+rd))
最坏情况
O(n2)
O(n2)
O(n2)
O(nlogn)
O(nlogn)
O(d(n+rd))
辅助存储
O(1)
O(1)
O(logn)
O(1)
O(n)
O(rd)
插入,交换,选择,归并,基数排序
几个结论
?(1)平均时间性能快速排序最佳,但最坏情况下的
时间性能不如堆排序和归并排序,
?(2)简单排序以, 直接插入排序, 最简单,当序列
,基本有序, 或 n较小时,它是最佳排序方法,通
常用它与, 先进的排序方法, 结合使用,
?(3)基数排序最适合 n很大而关键字较小的序列
?(4)从稳定性看,归并排序,基数排序和, 简单排
序法, 是稳定的 ;而快速排序,堆排序和 SHELL排
序是不稳定的,
?(5)稳定性由方法本身决定,不稳定的方法总能举
出使其不稳定的实例,
习题与实验
?理论题,10.1,10.3,10.7,10.12
?算法设计题,10.23,10.33
? 10.1 概述
? 10.2 插入排序
? 10.2.1 直接插入排序
? 10.2.3 shell排序
? 10.3 交换排序（快速排序）
? 10.4 选择排序
? 10.4.1 简单选择排序
? 10.4.3 堆排序
? 10.5 归并排序
? 10.6 基数排序
? 10.7 各种排序方法的比较讨论
10.1 内部排序 概述
?排序 (Sorting):
? 将数据元素 (或记录 )的一个任意序列,重新排列成
一个按关键字有序的序列。
? 排序方法的稳定性：
? 对关键字相同的数据元素，排序前后它们的领先关
系保持不变，则称该排序方法是稳定的。反之，称
该排序方法是不稳定的。
? 内部排序
? 待排序记录存放在计算机的内存中进行排序。
? 外部排序
? 待排序记录的数量很大，以致内存一次不能容纳全
部记录，在排序过程中尚需对外存进行访问的排序。
排序的分类
? 按排序过程依据的不同原则进行分类：
? 插入排序、
? 交换排序、
? 选择排序、
? 归并排序和
? 基数排序
? 按工作量分类，可以分为三类：
? (1)简单的排序方法,其时间复杂度为 O(n2);
? (2)先进的排序方法,其时间复杂度为 O(nlog2n);
? (3)基数排序，其时间复杂度为 O(dn);
排序的基本操作和
记录的存储方式
? 排序过程中需要的两种基本操作：
? （ 1）比较关键字的大小；
? （ 2）将记录从一个位置移至另一个位置。
? 待排序记录序列可有下列三种存储方式：
? （ 1）记录存放在一组连续的存储单元中；类似于线性表
的顺序存储结构，记录次序由存储位置决定，实现排序需
移动记录。
? （ 2）记录存放在静态链表中；记录次序由指针指示，实
现排序不需移动记录，仅需修改指针。 ---链排序
? （ 3）记录本身存放在一组连续的存储单元中，同时另设
指示各个记录存储位置的地址向量，排序过程中不移动记
录本身，而移动地址向量中相应记录的地址。排序结束后
再根据地址调整记录的存储位置 。 ---地址排序
待排序记录的数据类型
?#define MAXSIZE 20
?typedef int KeyType;
?typedef struct{
? KeyType key;
? InfoType otherinfo;
?}RcdType;
?typedef struct{
? RedType r[MAXSIZE+1];
? int length;
?}SqList;
10.2 插入排序
10.2.1 直接插入排序
? 例：序列为 {49,38,65,97,76,13,27,49}
? {(49),38,65,97,76,13,27,49}
? (38) {(38,49),65,97,76,13,27,49}
? (65) {(38,49,65),97,76,13,27,49}
? (97) {(38,49,65,97),76,13,27,49}
? (76) {(38,49,65,76,97),13,27,49}
? (13) {(13,38,49,65,76,97),27,49}
? (27) {(13,27,38,49,65,76,97),49}
? (49) {(13,27,38,49,49,65,76,97)}
直接插入排序算法
void InsertSort(SqList &L)
{ for(i=2; i<=L.length; ++i)
if ( LT(L.r[i].key,L.r[i-1].key) ){
L.r[0] = L.r[i]; // 复制为哨兵
for(j=i-1; LT(L.r[0].key,L.r[j].key); --j)
L.r[j+1] = L.r[j]; // 记录后移
L.r[j+1] = L.r[0];
}} // InsertSort
时间：最坏情形判断与移动各接近 n(n+1)/2;
最好情形判断 n次，无移动；故时间复杂度,O(n2)
空间：一个辅助空间
10.2.2 Shell排序算法
?基本思想：
? 先将整个待排序记录序列分割成若干
子序列分别进行直接插入排序，待整个
序列“基本有序”时，再对全体记录进
行一次直接插入排序。
?算法复杂度,O(n3/2)
Shell排序举例 （非稳定的）
二趟结果 {13,04,49,38,27,49,55,65,97,76}
增量取 1,13,04,49,38,27,49,55,65,97,76
三趟结果 {04,13,27,38,49,49,55,65,76,97}
一趟结果 {13,27,49,55,04,49,38,65,97,76}
增量取 3,13 55 38 76
27 04 65
49 49 97
例,{49,38,65,97,76,13,27,49,55,04}
增量取 5,49 13
38 27
65 49
97 55
76 04
10.3 交换排序
1,冒泡排序（ 其时间复杂度 O(n2)）
初
始
关
键
字
第
一
趟
排
序后
第
二
趟
排
序后
第
三
趟
排
序后
第
四
趟
排
序后
第
五
趟
排
序后
第
六
趟
排
序后
例,49 38 38 38 38 13 13
38 49 49 49 13 27 27
65 65 65 13 27 38 38
97 76 13 27 49 49
76 13 27 49 49
13 27 49 65
27 49 76
49 97
2,快速排序
----- 对冒泡排序的一种改进
?基本思想：
? 通过一趟排序将待排序记录分割成独
立的两部分，其中一部分的关键字均比
另一部分的关键字小，则可分别对这两
部分记录继续分别进行排序，以达到整
个序列有序。
快速排序举例
初始关键字,{49,38,65,97,76,13,27,49}
pivot key 49
jji
1次交换后,{27,38,65,97,76,13，, 49}
i ji
2次交换后,{27,38，, 97,76,13,65,49}
i jj
3次交换后,{27,38,13,97,76，, 65,49}
i ji
4次交换后,{27,38,13，, 76,97,65,49}
ji j
一趟完成后,{27,38,13,49,76,97,65,49}
快速排序分析
? 快速排序的平均时间为 T(n) = knlog(n)
?k为某个常数因子
? 经验表明,在同数量级的排序方法中,快速排序
的常数因子 k最小,
? 就平均时间而言,快速排序是最好的,
? 若初始序列按关键字基本有序,快速排序蜕化
为起泡排序,其时间复杂度为 O(n2)。
? 改进的方法，用“三者取中”的法则选取枢轴
记录（ pivotkey).
快速排序举例
初始关键字,{49,38,65,97,76,13,27,49}
pivot key 49
jji
1次交换后,{27,38,65,97,76,13，, 49}
i ji
2次交换后,{27,38，, 97,76,13,65,49}
i jj
3次交换后,{27,38,13,97,76，, 65,49}
i ji
4次交换后,{27,38,13，, 76,97,65,49}
ji j
一趟完成后,{27,38,13,49,76,97,65,49}
快速排序算法（一）
int Partition(SqList &L,int low,int high)
{L.r[0] = L.r[low]; // 用子表的第一记录作枢轴记录
pivotkey = L.r[low].key;
while(low<high){
while(low<high && L.r[high].key>=pivotkey) --high;
L.r[low] = L.r[high]; // 将比 pivotkey 小的记录移到低端
while(low<high && L.r[low].key<=pivotkey) ++low;
L.r[high] = L.r[low]; // 将比 pivotkey 大的记录移到高端
}
L.r[low] = l.r[0];
return low;
}
快速排序算法（二）
void Qsort(SqList &L,int low,int high)
{ if(low<high){
pivotloc = Partition(L,low,high);
Qsort(L,low,pivotloc-1);
Qsort(L,pivotloc+1,high);
}
} // QSort
void QuickSort(SqList &L){
Qsort(L,1,L.length);
} // QuickSort
10.4 选择排序
10.4.1,简单选择排序 （ 其时间复杂度 O(n2)）
? 基本思想：
? 每一趟在序列的后 n-i+1(i=1,2,...,n-1)个记
录中选取关键字最小的记录作为第 i个记录。
void SelectSort(SqList &L)
{ for(i=1; i<L.length; ++i){
j = SelectMinKey(L,i); // 在 L.r[i..length]中选择 key最小
if(i != j) L.r[i] <--> L.r[j]; // 与第 i个记录交换
}
} // SelectSort
初始关键字,{49,38,65,97,76,13,27,49}
第一次交换,{13,38,65,97,76,49,27,49}
i j
10.4.3 堆排序
? 堆的定义：
?n个元素的序列 {k1,k2,...,kn}当且仅当满足下
列条件时，称之为堆。
ki <= k2i ki >= k2i
ki <= k2i+1 ki >= k2i+1或 ( i = 1,2,...,[n/2] )
堆举例：
{96,83,27,38,11,09)
{12,36,24,85,47,30,53,91}
96
83
38 11 09
27
12
36
85 47 30
24
53
91
完全二叉树,且所有非叶
结点的值均不大于 (不小
于 )其左、右孩子结点的值
实现堆要解决的问题
? （ 1）如何从一个无序序列建成一个堆？
? （ 2）如何在输出堆顶元素之后，调整剩余元
素成为一个新的堆？
12
36
85 47 30
24
53
91 (a)
91
36
85 47 30
24
53
12 (b)
91
36
85 47 30
24
53
(c)
24
36
85 47 91
30
53
(d)
无序序列建成一个堆 （从第 n/2到 1个元素）
{49,38,65,97,76,13,27,49}
49
38
49 76 13
65
27
97 (b)
49
38
49 76 65
13
27
97 (c)
49
38
97 76 13 27
49 (a)
65
49
38
49 76 65
13
27
97 (d)
13
38
49 76 65
27
49
97 (e)
10.5 归并排序 (Merging Sort)
? 将两个或两个以上的有序表组合成一个新的有序表
? 2-路归并举例,
初始关键字, [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]
2-路归并算法
? void Merge(RcdType SR[],RcdType &TR[],int i,int m,int n)
? { // 将有序的 SR[i..m]和 SR[m+1..n]合并为有序的 TR[i..n]
? for(j=m+1,k=i; i<=m&&j<=n; ++k)
? { if LQ(SR[i].key,SR[j].key) TR[k] = SR[i++];
? else TR[k] = SR[j++];
? }
? if(i<=m) TR[k..n] = SR[i..m]; //复制剩余的 SR[i..m]
? if(j<=n) TR[k..n] = SR[j..n]; //复制剩余的 SR[j..n]
? } // Merge
归并算法的特点
? 需要辅助空间, O(n)
? 整个归并需要 [log2n] 趟
? 时间复杂度, O(n log2n)
? 它是稳定的排序方法
? 思想可以推广到, 多 -路归并,
10.6 基数排序 (Radix Sorting)
? 不需要进行关键字之间的比较
? 借助多关键字排序的思想对单关键字排序
? 10.6.1 多关键字排序
? ?2<?3<?4<?5<?6<?7<?8<?9<?10<?J<?Q<?K<?A<
? ?2<?3<?4<?5<?6<?7<?8<?9<?10<?J<?Q<?K<?A<
? ?2<?3<?4<?5<?6<?7<?8<?9<?10<?J<?Q<?K<?A<
? ?2<?3<?4<?5<?6<?7<?8<?9<?10<?J<?Q<?K<?A
? 花色 (?<?<?<?)优先于面值 (2<3<...<A)
? 最高位优先 (MSD),分成子序列分别排序
? 最高位优先 (LSD),通过若干次, 分配, 和, 收集,
10.6.2 基数排序
?借助,分配”和“收集“两种操作对单关
键字进行排序 。 例如,
? 278->109->063->930->589->184->505->269->008->083
0 1 32 4 5 6 7 8 9
278 109063930 184 505
589
269
008083
930->063->083->184->505->278->008->109->589->269
930->063->083->184->505->278->008->109->589->269
0 1 32 4 5 6 7 8 9
278
109
063930
184
505
589
269008
184
505->008->109->930->063->269->278->083->184->589
0 1 32 4 5 6 7 8 9
505008 109 930
063
269
278
083
083
589
008->063->083->109->184->269->278->505->589->930
基数排序分析 (d个关键字的取值范围 rd）
?“收集”重复的次数为 d;
?一轮“分配”的次数为 n+rd;
?时间复杂度为 O(d(n+rd));
?链式基数排序所需辅助存储量为 O(n)。
10.7 各种排序方法的比较讨论
排序方法
简单排序
Shell排序
快速排序
堆排序
归并排序
基数排序
平均时间
O(n2)
O(n3/2)
O(nlogn)
O(nlogn)
O(nlogn)
O(d(n+rd))
最坏情况
O(n2)
O(n2)
O(n2)
O(nlogn)
O(nlogn)
O(d(n+rd))
辅助存储
O(1)
O(1)
O(logn)
O(1)
O(n)
O(rd)
插入,交换,选择,归并,基数排序
几个结论
?(1)平均时间性能快速排序最佳,但最坏情况下的
时间性能不如堆排序和归并排序,
?(2)简单排序以, 直接插入排序, 最简单,当序列
,基本有序, 或 n较小时,它是最佳排序方法,通
常用它与, 先进的排序方法, 结合使用,
?(3)基数排序最适合 n很大而关键字较小的序列
?(4)从稳定性看,归并排序,基数排序和, 简单排
序法, 是稳定的 ;而快速排序,堆排序和 SHELL排
序是不稳定的,
?(5)稳定性由方法本身决定,不稳定的方法总能举
出使其不稳定的实例,
习题与实验
?理论题,10.1,10.3,10.7,10.12
?算法设计题,10.23,10.33
