1
9.5 归并排序
1、归并排序的基本思想是,将两个（或以上）的
有序表组成新的有序表。（归并排序主要是二路归
并排序）
2、二路归并排序,可以把一个长度为 n 的无序序
列看成是 n 个长度为 1 的有序子序列,首先做
两两归并，得到 ?n / 2? 个长度为 2 的 有序 子序
列 ；再做两两归并,…,如此重复，直到最后得
到一个长度为 n 的有序序列。
例 8,关键字序列 T= （ 21,25,49,25*,93,62，
72,08,37,16,54），请给出归并排序的具体实
现过程。
2
21 25 25* 93 62 72 08 37 16 5449
21 25 25* 49 62 93 08 72 16 37 54
16 37 54
21 25 25* 49 08 62 72 93
08 21 25 25* 49 62 72 93
08 16 21 25 25* 37 49 54 62 72 93
len=1
len=2
len=4
len=8
len=16
16 37 54
整个归并排序仅需 ?log2n ?趟
3
一次二路归并排序算法的 C语言程序
void Merge(DataType a[],int n,DataType swap[],int k)
/*k为有序子数组的长度，一次排序后的有序子序列存于数组
swap中 */
{ int m = 0,u1,l2,i,j,u2;
int l1 = 0; /*第一个有序子数组下界为 0*/
while(l1+k <= n-1)
{ l2 = l1 + k; /*计算第二个有序子数组下界 */
u1 = l2 - 1; /*计算第一个有序子数组上界 */
u2 = (l2+k-1 <= n-1)? l2+k-1,n-1;/*计算第二个有序子数组上界 */
/*两个有序子数组合并 */
for(i = l1,j = l2; i <= u1 && j <= u2; m++)
{ if(a[i].key <= a[j].key)
{ swap[m] = a[i];
i++;
}
4
else { swap[m]=a[j]; j++; }
}
/*子数组 2已归并完，将子数组 1中剩余的元素存到数组 swap中 */
while(i <= u1) { swap[m] = a[i]; m++; i++; }
/*子数组 1已归并完，将子数组 2中剩余的元素存到数组 swap中 */
while(j <= u2) { swap[m] = a[j]; m++; j++; }
l1 = u2 + 1;
}
/*将原始数组中只够一组的数据元素顺序存放到数组 swap中 */
for(i = l1; i < n; i++,m++) swap[m] = a[i];
}
5
3,二路归并排序算法分析：
? 时间效率,O(nlog2n)
因为在递归的归并排序算法中，函数 Merge( )做一趟两路归
并排序，需要调用 merge ( )函数 ?n/(2len)? ? O(n/len) 次，
而每次 merge( )要执行比较 O(len)次，另外整个归并过程有
?log2n?,层”,所以算法总的时间复杂度为 O(nlog2n)。
? 空间效率,O(n)
因为需要一个与原始序列同样大小的辅助序列。这正是此
算法的缺点。
? 稳定性,稳定
6
9.6 基数排序
要讨论的问题：
1,什么是, 多关键字, 排序？ 实现方法？
2,单逻辑关键字怎样, 按位值, 排序？
基数排序的基本思想是：
借助多关键字排序的思想对单逻辑关键字进行排
序。即：用关键字 不同的位值 进行排序。
7
1,什么是,多关键字,排序？实现方法？
例 1：对一副扑克牌该如何排序？
若规定花色和面值的顺序关系为：
花色, ? ? ? ? ? ? ?
面值,2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A
则 可以 先按花色 排序，花色相同者 再按面值 排序；
也可以先按面值排序，面值相同者再按花色排序。
例 2：职工分房该如何排序？
我校规定,先以总分 排序（职称分＋工龄分）；
总分相同者,再按配偶总分 排序，其次按配偶职
称、工龄、人口 …… 等等排序。
以上两例都是典型的 多关键字 排序！
8
多关键字排序的实现方法通常有两种：
? 最高位优先法 MSD (Most Significant Digit first)
例,对一副扑克牌该如何排序？
答,若规定 花色为第一 关键字（高位）,面值为第二 关键字
（低位），则使用 MSD和 LSD方法都可以达到排序目的。
MSD方法的思路,先设立 4个花色“箱”，将全部牌按花色分
别归入 4个箱内（每个箱中有 13张牌）；然后对每个箱中的牌
按面值进行插入排序（或其它稳定算法）。
LSD方法的思路,先按面值分成 13堆（每堆 4张牌），然后对
每堆中的牌按花色进行排序（用插入排序等稳定的算法）。
想一想：用哪种方法更快些？
? 最低位优先法 LSD (Least Significant Digit first)
9
2,单逻辑 关键字怎样,按位值,排序？
设 n 个记录的序列为,{V0,V1,…,Vn-1 }，可以把每
个记录 Vi 的 单关键码 Ki 看成是一个 d元组 （ Ki1,
Ki2,…,Kid）,则其中的每一个分量 Kij ( 1? j ? d )
也可看成是一个关键字。
4
注 1,Ki1＝最高位, Kid＝最低位； Ki共有 d位, 可看成 d元组；
注 2,每个分量 Kij (1 ? j ? d ) 有 radix种取值, 则称 radix为 基数 。
26
(9,8,4) (0,1,…,9)
（ a,b,…,z ）(d,i,a,n)
3 10例 1,关键码 984可以看成是 元组；基数 radix为 。
例 2,关键码 dian可以看成是 元组；基数 radix为 。
思路：
10
因为有分组，故此算法需递归实现。
讨论,是借用 MSD方式来排序呢，还是借用 LSD方式？
例,初始关键字序列 T=（ 32,13,27,32*,19,33），请分别
用 MSD和 LSD进行排序，并讨论其优缺点。
法 1（ MSD）,原始序列,32,13,27,32*,19,33
先按高位 Ki1 排序,（ 13,19）,27,（ 32,32*,33）
再按低位 Ki2 排序, 13,19, 27,32,32*,33
法 2（ LSD）,原始序列,32,13,27,32*,19, 33
先按低位 Ki2排序,32,32*,13,33,27,19
再按高位 Ki1排序,13,19,27,32,32*,33
无需分组，易编程实现！
11
例, T=（ 02,77,70,54,64,21,55,11），用 LSD排序。
分析：
①各关键字可视为 2元组 ；②每位的取值范围是,0-9；即 基数
radix ＝ 10 。 因此，特设置 10个队列，并编号为 0-9。
11
55
21
64
54
70
77
02
原始序列
1
2
3
4
5
6
7
8
先对低位扫描 出队
0
1
2
3
4
5
6
7
8
9
10个队列
计算机怎样实现 LSD算法？
分配
过程 收集过程
下一步
77
55
64
54
02
11
21
701
2
3
4
5
6
7
8
出队后序列
77
55
54,64
21
70
02
又称散列过程！
,11
12
0
1
2
3
4
5
6
7
8
9
再次入队
再次出队再对高位扫描
小结,排序时经过了反复的“分配”和“收集”过程。当对关
键字所有的位进行扫描排序后，整个序列便从无序变为有序
了。
77
55
64
54
02
11
21
701
2
3
4
5
6
7
8
出队后序列
70
64
54
21
11
02
再次
分配 再次收集 7770
64
55
54
21
11
02
再次出队后序列
这种 LSD排序方法称为,基数排序
,77
,55
13
* 基数排序算法的基本思想：
设待排序的数据元素关键字是 m位 d进制整数（不足 m位
的关键字在高位补 0），设置 d个桶，令其编号分别为
0,1,2,…,d-1。 首先，按关键字最低位的数值依次把各数据
元素放到相应的桶中；然后，按照桶号从小到大和进入桶中
数据元素的先后次序收集分配在各桶中的数据元素；这样，
就形成了数据元素集合的一个新的排列，称这样的一次排序
过程为 一次基数排序 。 再对一次基数排序得到的数据元素序
列按关键字次低位的数值依次把各数据元素放到相应的桶中，
然后按照桶号从小到大和进入桶中数据元素的先后次序收集
分配在各桶中的数据元素。 这样的过程重复进行，当完成了
第 m次基数排序后，就得到了排好序的数据元素序列。
14
讨论,所用 队列 是顺序结构，浪费空间，能否改用 链式结构？
用链队列来实现基数排序 — 链式基数排序
实现思路,针对 d 元组 中的每一位分量，把原始 链表 中
的所有记录,按 Kij的取值，让 j = d,d-1,…,1,
① 先,分配,到 radix个 链队列 中去；
② 然后再按各 链队列 的顺序，依次把记录从 链队列 中
,收集,起来；
③ 分别用这种“分配”、“收集”的运算逐趟进行排序；
④ 在最后一趟“分配”、“收集” 完成后，所有记录就
按其关键码的值从小到大排好序了。
能！
15
请实现以下关键字序列的 链式基数排序,
T=（ 614,738,921,485,637,101,215,530,790,306）
例,
614 921 485 637738 101 215 530 790 306
第一趟分配
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
614 738921 485 637
101 215
530
790
306
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
原始序列 静态 链表：
r[0]→
（从最低位 i = 3开始排序,f[ ] 是队首指针,e[ ] 为队尾指针）
第一趟收集 （让队尾指针 e[i] 链接到下一 非空队首 指针 f[i+1 ] 即可）
530 790 921 101 614 485 215 306 637 738r[0]→
16
第一趟收集的结果：
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
614
738
921 485
637
101
215
530 790
306
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
第二趟分配 （按次低位 i = 2 ）
530 790 921 101 614 485 215 306 637 738
第二趟收集 （让队尾指针 e[i] 链接到下一非空队首指针 f[i+1 ] ）
530 790921101 614 485215306 637 738
r[0]→
r[0]→
17
第二趟收集的结果：
530 790921101 614 485215306 637 738
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
614 738 921485
637
101 215 530
790
306
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
第三趟分配 （按最高位 i = 1 ）
第三趟收集 （让队尾指针 e[i] 链接到下一非空队首指针 f[i+1 ] ）
530 790 921101 614485215 306 637 738
r[0]→
r[0]→
排序结束！
18
基于链式队列的基数排序算法：
void RadixSort(DataType a[],int n,int m,int d)
/*对数据元素 a[0]--a[n-1]进行关键字为 m位 d进制整型数值的基数排
序，桶采用链式队列结构 */
{ int i,j,k,power = 1;
LQueue *tub;
tub = (LQueue *)malloc(sizeof(LQueue )* d);
for(i = 0; i < d; i++)
QueueInitiate(&tub[i]);
//进行 m次放和收
for(i = 0; i < m; i++)
{ if(i == 0) power = 1;
else power = power *d;
19
//将数据元素按关键字第 k位的大小放到相应的队列中
for(j = 0; j < n; j++)
{ k = a[j].key /power - (a[j].key /(power * d)) * d;
QueueAppend(&tub[k],a[j]);
}
//顺序回收各队列中的数据元素
for(j = 0,k = 0; j < d; j++)
while(QueueNotEmpty(tub[j]) != 0)
{ QueueDelete(&tub[j],&a[k]);
k++;
}
}
}
20
基数排序算法分析
时间复杂度为, O (mn)。
空间复杂度, O(n）,
稳定性,稳定 。 (一直前后有序 )。
特点,不用比较和移动，改用分配和收集，时间效率高！
21
9.7 各种内部排序方法的性能比较
排序方法 最好情况 平均时间 最坏情况 辅助存储 稳定性
简单排序 O(n) O(n2) O(n2) O(1） 稳定
快速排序 O(nlgn ) O(nlgn) O(n2) O(lgn) 不稳定
堆排序 O(nlgn ) O(nlgn ) O(nlgn) O(1） 不稳定
归并排序 O(nlgn ) O(nlgn ) O(nlgn) O(n） 稳定
基数排序
(基于链式
队列）
O(mn) O(mn) O(mn) O(n) 稳定
简单选择 O(n2) O(n2) O(n2) O(1） 不稳定
直接插入 O(n) O(n2) O(n2) O(1） 稳定
冒泡 O(n) O(n2) O(n2) O(1） 稳定
22
课练 1,若初始记录基本有序，则选用哪些排序方法比较适合？
若初始记录基本无序，则最好选用哪些排序方法？请解释理
由（排序方法各列举两种即可）。
答,基本有序时可选用直接插入、简单选择、堆排序、
冒泡排序、归并排序,(希尔排序 )等方法，其中插入
排序和冒泡应该是最快的。因为只有比较动作，无需
移动元素。此时平均时间复杂度为 O(n)；
无序的情况下最好选用快速排序、希尔排序、简单选
择排序等，这些算法的共同特点是，通过, 振荡, 让
数值相差不大但位置差异很大的元素尽快到位。
9.5 归并排序
1、归并排序的基本思想是,将两个（或以上）的
有序表组成新的有序表。（归并排序主要是二路归
并排序）
2、二路归并排序,可以把一个长度为 n 的无序序
列看成是 n 个长度为 1 的有序子序列,首先做
两两归并，得到 ?n / 2? 个长度为 2 的 有序 子序
列 ；再做两两归并,…,如此重复，直到最后得
到一个长度为 n 的有序序列。
例 8,关键字序列 T= （ 21,25,49,25*,93,62，
72,08,37,16,54），请给出归并排序的具体实
现过程。
2
21 25 25* 93 62 72 08 37 16 5449
21 25 25* 49 62 93 08 72 16 37 54
16 37 54
21 25 25* 49 08 62 72 93
08 21 25 25* 49 62 72 93
08 16 21 25 25* 37 49 54 62 72 93
len=1
len=2
len=4
len=8
len=16
16 37 54
整个归并排序仅需 ?log2n ?趟
3
一次二路归并排序算法的 C语言程序
void Merge(DataType a[],int n,DataType swap[],int k)
/*k为有序子数组的长度，一次排序后的有序子序列存于数组
swap中 */
{ int m = 0,u1,l2,i,j,u2;
int l1 = 0; /*第一个有序子数组下界为 0*/
while(l1+k <= n-1)
{ l2 = l1 + k; /*计算第二个有序子数组下界 */
u1 = l2 - 1; /*计算第一个有序子数组上界 */
u2 = (l2+k-1 <= n-1)? l2+k-1,n-1;/*计算第二个有序子数组上界 */
/*两个有序子数组合并 */
for(i = l1,j = l2; i <= u1 && j <= u2; m++)
{ if(a[i].key <= a[j].key)
{ swap[m] = a[i];
i++;
}
4
else { swap[m]=a[j]; j++; }
}
/*子数组 2已归并完，将子数组 1中剩余的元素存到数组 swap中 */
while(i <= u1) { swap[m] = a[i]; m++; i++; }
/*子数组 1已归并完，将子数组 2中剩余的元素存到数组 swap中 */
while(j <= u2) { swap[m] = a[j]; m++; j++; }
l1 = u2 + 1;
}
/*将原始数组中只够一组的数据元素顺序存放到数组 swap中 */
for(i = l1; i < n; i++,m++) swap[m] = a[i];
}
5
3,二路归并排序算法分析：
? 时间效率,O(nlog2n)
因为在递归的归并排序算法中，函数 Merge( )做一趟两路归
并排序，需要调用 merge ( )函数 ?n/(2len)? ? O(n/len) 次，
而每次 merge( )要执行比较 O(len)次，另外整个归并过程有
?log2n?,层”,所以算法总的时间复杂度为 O(nlog2n)。
? 空间效率,O(n)
因为需要一个与原始序列同样大小的辅助序列。这正是此
算法的缺点。
? 稳定性,稳定
6
9.6 基数排序
要讨论的问题：
1,什么是, 多关键字, 排序？ 实现方法？
2,单逻辑关键字怎样, 按位值, 排序？
基数排序的基本思想是：
借助多关键字排序的思想对单逻辑关键字进行排
序。即：用关键字 不同的位值 进行排序。
7
1,什么是,多关键字,排序？实现方法？
例 1：对一副扑克牌该如何排序？
若规定花色和面值的顺序关系为：
花色, ? ? ? ? ? ? ?
面值,2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A
则 可以 先按花色 排序，花色相同者 再按面值 排序；
也可以先按面值排序，面值相同者再按花色排序。
例 2：职工分房该如何排序？
我校规定,先以总分 排序（职称分＋工龄分）；
总分相同者,再按配偶总分 排序，其次按配偶职
称、工龄、人口 …… 等等排序。
以上两例都是典型的 多关键字 排序！
8
多关键字排序的实现方法通常有两种：
? 最高位优先法 MSD (Most Significant Digit first)
例,对一副扑克牌该如何排序？
答,若规定 花色为第一 关键字（高位）,面值为第二 关键字
（低位），则使用 MSD和 LSD方法都可以达到排序目的。
MSD方法的思路,先设立 4个花色“箱”，将全部牌按花色分
别归入 4个箱内（每个箱中有 13张牌）；然后对每个箱中的牌
按面值进行插入排序（或其它稳定算法）。
LSD方法的思路,先按面值分成 13堆（每堆 4张牌），然后对
每堆中的牌按花色进行排序（用插入排序等稳定的算法）。
想一想：用哪种方法更快些？
? 最低位优先法 LSD (Least Significant Digit first)
9
2,单逻辑 关键字怎样,按位值,排序？
设 n 个记录的序列为,{V0,V1,…,Vn-1 }，可以把每
个记录 Vi 的 单关键码 Ki 看成是一个 d元组 （ Ki1,
Ki2,…,Kid）,则其中的每一个分量 Kij ( 1? j ? d )
也可看成是一个关键字。
4
注 1,Ki1＝最高位, Kid＝最低位； Ki共有 d位, 可看成 d元组；
注 2,每个分量 Kij (1 ? j ? d ) 有 radix种取值, 则称 radix为 基数 。
26
(9,8,4) (0,1,…,9)
（ a,b,…,z ）(d,i,a,n)
3 10例 1,关键码 984可以看成是 元组；基数 radix为 。
例 2,关键码 dian可以看成是 元组；基数 radix为 。
思路：
10
因为有分组，故此算法需递归实现。
讨论,是借用 MSD方式来排序呢，还是借用 LSD方式？
例,初始关键字序列 T=（ 32,13,27,32*,19,33），请分别
用 MSD和 LSD进行排序，并讨论其优缺点。
法 1（ MSD）,原始序列,32,13,27,32*,19,33
先按高位 Ki1 排序,（ 13,19）,27,（ 32,32*,33）
再按低位 Ki2 排序, 13,19, 27,32,32*,33
法 2（ LSD）,原始序列,32,13,27,32*,19, 33
先按低位 Ki2排序,32,32*,13,33,27,19
再按高位 Ki1排序,13,19,27,32,32*,33
无需分组，易编程实现！
11
例, T=（ 02,77,70,54,64,21,55,11），用 LSD排序。
分析：
①各关键字可视为 2元组 ；②每位的取值范围是,0-9；即 基数
radix ＝ 10 。 因此，特设置 10个队列，并编号为 0-9。
11
55
21
64
54
70
77
02
原始序列
1
2
3
4
5
6
7
8
先对低位扫描 出队
0
1
2
3
4
5
6
7
8
9
10个队列
计算机怎样实现 LSD算法？
分配
过程 收集过程
下一步
77
55
64
54
02
11
21
701
2
3
4
5
6
7
8
出队后序列
77
55
54,64
21
70
02
又称散列过程！
,11
12
0
1
2
3
4
5
6
7
8
9
再次入队
再次出队再对高位扫描
小结,排序时经过了反复的“分配”和“收集”过程。当对关
键字所有的位进行扫描排序后，整个序列便从无序变为有序
了。
77
55
64
54
02
11
21
701
2
3
4
5
6
7
8
出队后序列
70
64
54
21
11
02
再次
分配 再次收集 7770
64
55
54
21
11
02
再次出队后序列
这种 LSD排序方法称为,基数排序
,77
,55
13
* 基数排序算法的基本思想：
设待排序的数据元素关键字是 m位 d进制整数（不足 m位
的关键字在高位补 0），设置 d个桶，令其编号分别为
0,1,2,…,d-1。 首先，按关键字最低位的数值依次把各数据
元素放到相应的桶中；然后，按照桶号从小到大和进入桶中
数据元素的先后次序收集分配在各桶中的数据元素；这样，
就形成了数据元素集合的一个新的排列，称这样的一次排序
过程为 一次基数排序 。 再对一次基数排序得到的数据元素序
列按关键字次低位的数值依次把各数据元素放到相应的桶中，
然后按照桶号从小到大和进入桶中数据元素的先后次序收集
分配在各桶中的数据元素。 这样的过程重复进行，当完成了
第 m次基数排序后，就得到了排好序的数据元素序列。
14
讨论,所用 队列 是顺序结构，浪费空间，能否改用 链式结构？
用链队列来实现基数排序 — 链式基数排序
实现思路,针对 d 元组 中的每一位分量，把原始 链表 中
的所有记录,按 Kij的取值，让 j = d,d-1,…,1,
① 先,分配,到 radix个 链队列 中去；
② 然后再按各 链队列 的顺序，依次把记录从 链队列 中
,收集,起来；
③ 分别用这种“分配”、“收集”的运算逐趟进行排序；
④ 在最后一趟“分配”、“收集” 完成后，所有记录就
按其关键码的值从小到大排好序了。
能！
15
请实现以下关键字序列的 链式基数排序,
T=（ 614,738,921,485,637,101,215,530,790,306）
例,
614 921 485 637738 101 215 530 790 306
第一趟分配
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
614 738921 485 637
101 215
530
790
306
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
原始序列 静态 链表：
r[0]→
（从最低位 i = 3开始排序,f[ ] 是队首指针,e[ ] 为队尾指针）
第一趟收集 （让队尾指针 e[i] 链接到下一 非空队首 指针 f[i+1 ] 即可）
530 790 921 101 614 485 215 306 637 738r[0]→
16
第一趟收集的结果：
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
614
738
921 485
637
101
215
530 790
306
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
第二趟分配 （按次低位 i = 2 ）
530 790 921 101 614 485 215 306 637 738
第二趟收集 （让队尾指针 e[i] 链接到下一非空队首指针 f[i+1 ] ）
530 790921101 614 485215306 637 738
r[0]→
r[0]→
17
第二趟收集的结果：
530 790921101 614 485215306 637 738
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
614 738 921485
637
101 215 530
790
306
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
第三趟分配 （按最高位 i = 1 ）
第三趟收集 （让队尾指针 e[i] 链接到下一非空队首指针 f[i+1 ] ）
530 790 921101 614485215 306 637 738
r[0]→
r[0]→
排序结束！
18
基于链式队列的基数排序算法：
void RadixSort(DataType a[],int n,int m,int d)
/*对数据元素 a[0]--a[n-1]进行关键字为 m位 d进制整型数值的基数排
序，桶采用链式队列结构 */
{ int i,j,k,power = 1;
LQueue *tub;
tub = (LQueue *)malloc(sizeof(LQueue )* d);
for(i = 0; i < d; i++)
QueueInitiate(&tub[i]);
//进行 m次放和收
for(i = 0; i < m; i++)
{ if(i == 0) power = 1;
else power = power *d;
19
//将数据元素按关键字第 k位的大小放到相应的队列中
for(j = 0; j < n; j++)
{ k = a[j].key /power - (a[j].key /(power * d)) * d;
QueueAppend(&tub[k],a[j]);
}
//顺序回收各队列中的数据元素
for(j = 0,k = 0; j < d; j++)
while(QueueNotEmpty(tub[j]) != 0)
{ QueueDelete(&tub[j],&a[k]);
k++;
}
}
}
20
基数排序算法分析
时间复杂度为, O (mn)。
空间复杂度, O(n）,
稳定性,稳定 。 (一直前后有序 )。
特点,不用比较和移动，改用分配和收集，时间效率高！
21
9.7 各种内部排序方法的性能比较
排序方法 最好情况 平均时间 最坏情况 辅助存储 稳定性
简单排序 O(n) O(n2) O(n2) O(1） 稳定
快速排序 O(nlgn ) O(nlgn) O(n2) O(lgn) 不稳定
堆排序 O(nlgn ) O(nlgn ) O(nlgn) O(1） 不稳定
归并排序 O(nlgn ) O(nlgn ) O(nlgn) O(n） 稳定
基数排序
(基于链式
队列）
O(mn) O(mn) O(mn) O(n) 稳定
简单选择 O(n2) O(n2) O(n2) O(1） 不稳定
直接插入 O(n) O(n2) O(n2) O(1） 稳定
冒泡 O(n) O(n2) O(n2) O(1） 稳定
22
课练 1,若初始记录基本有序，则选用哪些排序方法比较适合？
若初始记录基本无序，则最好选用哪些排序方法？请解释理
由（排序方法各列举两种即可）。
答,基本有序时可选用直接插入、简单选择、堆排序、
冒泡排序、归并排序,(希尔排序 )等方法，其中插入
排序和冒泡应该是最快的。因为只有比较动作，无需
移动元素。此时平均时间复杂度为 O(n)；
无序的情况下最好选用快速排序、希尔排序、简单选
择排序等，这些算法的共同特点是，通过, 振荡, 让
数值相差不大但位置差异很大的元素尽快到位。
