,数据结构,
第十章 (下 )
数据结构
tjm
10.5 归并排序
归并 —— 将两个或两个以上的有序表组合成一个新的
有序表。
多路归并排序,将三个或三个以上有序子区间合并成
一个有序子区间的排序，称为多路归并排序。常见的
有三路归并排序、四路归并排序等，具体实现的方法
与二路归并排序类似。
算法 参见 P283,P284
2-路归并排序
排序过程：设初始序列含有 n个记录，则可看成 n个有
序的子序列，每个子序列长度为 1。
两两合并，得到 ?n/2?＋ 1个长度为 2或 1的有序子序列。
再两两合并,…… 如此重复，直至得到一个长度为 n
的有序序列为止。
数据结构
tjm
例：
初始关键字,[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]
算法评价
时间复杂度,T(n)=O(nlog2n)
空间复杂度,S(n)=O(n)
数据结构
tjm
例, 对 52张扑克牌按以下次序排序：
?2<?3<……< ?A<?2<?3<……< ?A<
?2<?3<……< ?A<?2<?3<……< ?A
两个关键字：花色（ ?<?<?<?）
面值（ 2<3<……<A ）
并且“花色”地位高于“面值”。
10.6 基数排序
10.6.1 多关键字排序
多关键字排序定义：
在实际应用中，有时的排序会需要按几种不同排序码
来排序。
对于多关键字排序（假设有 d个关键字），则可以按
第 1,2,…, d个关键字的顺序排序，也可以按第 d、
d-1,d-2,…, 2,1个关键字的顺序排序。
数据结构
tjm
最高位优先法（ MSD),先对最高位关键字 k1（ 如花色）
排序，将序列分成若干子序列，每个子序列有相同的 k1
值；然后让每个子序列对次关键字 k2（ 如面值）排序，
又分成若干更小的子序列；依次重复，直至就每个子序
列对最低位关键字 kd排序；最后将所有子序列依次连接
在一起成为一个有序序列。
最低位优先法 (LSD)：从最低位关键字 kd起进行排序，
然后再对高一位的关键字排序,…… 依次重复，直至对
最高位关键字 k1排序后，便成为一个有序序列。
MSD与 LSD不同特点：
按 MSD排序，必须将序列逐层分割成若干子序列，
然后对各子序列分别排序。
按 LSD排序，不必分成子序列，对每个关键字都是
整个序列参加排序；并且可不通过关键字比较，而
通过若干次分配与收集实现排序。
多关键字排序方法
数据结构
tjm
10.6.2 链式基数排序
基数排序：借助“分配”和“收集”对单逻辑关键字进
行排序的一种方法。
链式基数排序：用链表作存储结构的基数排序。
链式基数排序步骤：
设置 10个队列,f[i]和 e[i]分别为第 i个队列的头指针和尾
指针。
第一趟分配对最低位关键字（个位）进行，将链表中记
录分配至 10个链队列中，每个队列记录的关键字的个位
相同。
第一趟收集是改变所有非空队列的队尾记录的指针域，
令其指向下一个非空队列的队头记录，重新将 10个队列
链成一个链表。
重复上述两步，进行第二趟、第三趟分配和收集，分别
对十位、百位进行，最后得到一个有序序列。
数据结构
tjm
例：
初始状态：
278 109 063 930 589 184 505 269 008 083
109
589
269
278063930
083
184 505
008
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
一
趟
分
配
930 063 083 184 505 278 008 109 589 269
一趟收集：
数据结构
tjm
505 008 109 930 063 269 278 083 184 589
二趟收集：
083
184
589
063505
269
930
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
二
趟
分
配
008
109
278
930 063 083 184 505 278 008 109 589 269
一趟收集：
数据结构
tjm008 063 083 109 184 269 278 505 589 930
三趟收集：
109008
184
930
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
三
趟
分
配
063
083
269
278
505
589
505 008 109 930 063 269 278 083 184 589
二趟收集：
数据结构
tjm
算法 参见 P288
算法评价
分配,T(n)=O(n)
收集,T(n)=O(rd)
时间复杂度,T(n)=O(d(n+rd))
其中,n—— 记录数
d—— 关键字数
rd—— 关键字取值范围
空间复杂度,S(n)=2rd个队列指针 +n个指针域空
间 故它的空间复杂度为 O(rd)。
由于基数排序中值相同的元素的相对位置在分配
和收集中，不会发生变化，所以基数排序是一种
稳定的排序方法。
数据结构
tjm
初始状态：
1
278 109 063 930 589 184 505 269 008 0830
2 3 4 5 6 7 8 9 10
f[0]=0 e[0]=0
f[1]=0 e[1]=0
f[2]=0 e[2]=0
f[3]=0 e[3]=0
f[4]=0 e[4]=0
f[5]=0 e[5]=0
f[6]=0 e[6]=0
f[7]=0 e[7]=0
f[8]=0 e[8]=0
f[9]=0 e[9]=0
1 1
2 2
3 3
4 4
5
66
77
8
9
10
4
930 063 083 184 505 278 008 109 589 2690
3 10 6 7 1 9 2 5 8
数据结构
tjm
f[0]=0 e[0]=0
f[1]=0 e[1]=0
f[2]=0 e[2]=0
f[3]=0 e[3]=0
f[4]=0 e[4]=0
f[5]=0 e[5]=0
f[6]=0 e[6]=0
f[7]=0 e[7]=0
f[8]=0 e[8]=0
f[9]=0 e[9]=0
1
3
44
7 79
10
4
930 063 083 184 505 278 008 109 589 2690
3 10 6 7 1 9 2 5 8
一趟收集：
3
10
1
6
2
5
8
7
505 008 109 930 063 269 278 083 184 5890
9 2 4 3 8 1 10 6 5
二趟收集：
数据结构
tjm
7
505 008 109 930 063 269 278 083 184 5890
9 2 4 3 8 1 10 6 5
二趟收集：
f[0]=0 e[0]=0
f[1]=0 e[1]=0
f[2]=0 e[2]=0
f[3]=0 e[3]=0
f[4]=0 e[4]=0
f[5]=0 e[5]=0
f[6]=0 e[6]=0
f[7]=0 e[7]=0
f[8]=0 e[8]=0
f[9]=0 e[9]=04 4
7
9
2
8
7
9
2
8
9
008 063 083 109 184 269 278 505 589 9300
3 10 2 6 8 1 7 5 4
三趟收集：
3
1
10
6
5
数据结构
tjm
10.7 各种内部排序方法的比较讨论
从时间复杂度比较
从平均时间复杂度来考虑, 直接插入排序, 冒泡排序,
直接选择排序是三种简单的排序方法, 时间复杂度都为
O(n2),而快速排序, 堆排序, 二路归并排序的时间复杂
度都为 O(nlog2n),希尔排序的复杂度介于这两者之间 。
若从最好的时间复杂度考虑, 则直接插入排序和冒泡排
序的时间复杂度最好, 为 O(n),其它的最好情形同平均
情形相同 。 若从最坏的时间复杂度考虑, 则快速排序的
为 O(n2),直接插入排序, 冒泡排序, 希尔排序同平均情
形相同, 但系数大约增加一倍, 所以运行速度将降低一
半, 最坏情形对直接选择排序, 堆排序和归并排序影响
不大 。
数据结构
tjm
从空间复杂度比较
归并排序的空间复杂度最大，为 O(n)，快速排序的空间
复杂度为 O(log2n)，其它排序的空间复杂度为 O（ 1）。
从稳定性比较
直接插入排序, 冒泡排序, 归并排序是稳定的排序
方法, 而直接选择排序, 希尔排序, 快速排序, 堆
排序是不稳定的排序方法 。
从算法简单性比较
直接插入排序、冒泡排序、直接选择排序都是简单的排
序方法，算法简单，易于理解，而希尔排序、快速排序、
堆排序、归并排序都是改进型的排序方法，算法比简单
排序要复杂得多，也难于理解。
数据结构
tjm
各种内排序方法的选择
从时间复杂度选择
对元素个数较多的排序, 可以选快速排序, 堆排序, 归
并排序, 元素个数较少时, 可以选简单的排序方法 。
从空间复杂度选择
尽量选空间复杂度为 O（ 1）的排序方法，其次选空间复
杂度为 O(log2n)的快速排序方法，最后才选空间复杂度
为 O（ n）的 2-路归并的排序方法。
数据结构
tjm
一般选择规则
（ 1） 当待排序元素的个数 n较大, 排序码分布是随机,
而对稳定性不做要求时, 则采用快速排序为宜 。
（ 2） 当待排序元素的个数 n大, 内存空间允许, 且要
求排序稳定时, 则采用 2-路归并排序为宜 。
（ 3） 当待排序元素的个数 n大, 排序码分布可能会出
现正序或逆序的情形, 且对稳定性不做要求时, 则采
用堆排序或 2-路归并排序为宜 。
（ 4） 当待排序元素的个数 n小, 元素基本有序或分布
较随机, 且要求稳定时, 则采用直接插入排序为宜 。
（ 5） 当待排序元素的个数 n小, 对稳定性不做要求时,
则采用直接选择排序为宜, 若排序码不接近逆序, 也
可以采用直接插入排序 。 冒泡排序一般很少采用 。
第十章 (下 )
数据结构
tjm
10.5 归并排序
归并 —— 将两个或两个以上的有序表组合成一个新的
有序表。
多路归并排序,将三个或三个以上有序子区间合并成
一个有序子区间的排序，称为多路归并排序。常见的
有三路归并排序、四路归并排序等，具体实现的方法
与二路归并排序类似。
算法 参见 P283,P284
2-路归并排序
排序过程：设初始序列含有 n个记录，则可看成 n个有
序的子序列，每个子序列长度为 1。
两两合并，得到 ?n/2?＋ 1个长度为 2或 1的有序子序列。
再两两合并,…… 如此重复，直至得到一个长度为 n
的有序序列为止。
数据结构
tjm
例：
初始关键字,[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]
算法评价
时间复杂度,T(n)=O(nlog2n)
空间复杂度,S(n)=O(n)
数据结构
tjm
例, 对 52张扑克牌按以下次序排序：
?2<?3<……< ?A<?2<?3<……< ?A<
?2<?3<……< ?A<?2<?3<……< ?A
两个关键字：花色（ ?<?<?<?）
面值（ 2<3<……<A ）
并且“花色”地位高于“面值”。
10.6 基数排序
10.6.1 多关键字排序
多关键字排序定义：
在实际应用中，有时的排序会需要按几种不同排序码
来排序。
对于多关键字排序（假设有 d个关键字），则可以按
第 1,2,…, d个关键字的顺序排序，也可以按第 d、
d-1,d-2,…, 2,1个关键字的顺序排序。
数据结构
tjm
最高位优先法（ MSD),先对最高位关键字 k1（ 如花色）
排序，将序列分成若干子序列，每个子序列有相同的 k1
值；然后让每个子序列对次关键字 k2（ 如面值）排序，
又分成若干更小的子序列；依次重复，直至就每个子序
列对最低位关键字 kd排序；最后将所有子序列依次连接
在一起成为一个有序序列。
最低位优先法 (LSD)：从最低位关键字 kd起进行排序，
然后再对高一位的关键字排序,…… 依次重复，直至对
最高位关键字 k1排序后，便成为一个有序序列。
MSD与 LSD不同特点：
按 MSD排序，必须将序列逐层分割成若干子序列，
然后对各子序列分别排序。
按 LSD排序，不必分成子序列，对每个关键字都是
整个序列参加排序；并且可不通过关键字比较，而
通过若干次分配与收集实现排序。
多关键字排序方法
数据结构
tjm
10.6.2 链式基数排序
基数排序：借助“分配”和“收集”对单逻辑关键字进
行排序的一种方法。
链式基数排序：用链表作存储结构的基数排序。
链式基数排序步骤：
设置 10个队列,f[i]和 e[i]分别为第 i个队列的头指针和尾
指针。
第一趟分配对最低位关键字（个位）进行，将链表中记
录分配至 10个链队列中，每个队列记录的关键字的个位
相同。
第一趟收集是改变所有非空队列的队尾记录的指针域，
令其指向下一个非空队列的队头记录，重新将 10个队列
链成一个链表。
重复上述两步，进行第二趟、第三趟分配和收集，分别
对十位、百位进行，最后得到一个有序序列。
数据结构
tjm
例：
初始状态：
278 109 063 930 589 184 505 269 008 083
109
589
269
278063930
083
184 505
008
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
一
趟
分
配
930 063 083 184 505 278 008 109 589 269
一趟收集：
数据结构
tjm
505 008 109 930 063 269 278 083 184 589
二趟收集：
083
184
589
063505
269
930
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
二
趟
分
配
008
109
278
930 063 083 184 505 278 008 109 589 269
一趟收集：
数据结构
tjm008 063 083 109 184 269 278 505 589 930
三趟收集：
109008
184
930
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
三
趟
分
配
063
083
269
278
505
589
505 008 109 930 063 269 278 083 184 589
二趟收集：
数据结构
tjm
算法 参见 P288
算法评价
分配,T(n)=O(n)
收集,T(n)=O(rd)
时间复杂度,T(n)=O(d(n+rd))
其中,n—— 记录数
d—— 关键字数
rd—— 关键字取值范围
空间复杂度,S(n)=2rd个队列指针 +n个指针域空
间 故它的空间复杂度为 O(rd)。
由于基数排序中值相同的元素的相对位置在分配
和收集中，不会发生变化，所以基数排序是一种
稳定的排序方法。
数据结构
tjm
初始状态：
1
278 109 063 930 589 184 505 269 008 0830
2 3 4 5 6 7 8 9 10
f[0]=0 e[0]=0
f[1]=0 e[1]=0
f[2]=0 e[2]=0
f[3]=0 e[3]=0
f[4]=0 e[4]=0
f[5]=0 e[5]=0
f[6]=0 e[6]=0
f[7]=0 e[7]=0
f[8]=0 e[8]=0
f[9]=0 e[9]=0
1 1
2 2
3 3
4 4
5
66
77
8
9
10
4
930 063 083 184 505 278 008 109 589 2690
3 10 6 7 1 9 2 5 8
数据结构
tjm
f[0]=0 e[0]=0
f[1]=0 e[1]=0
f[2]=0 e[2]=0
f[3]=0 e[3]=0
f[4]=0 e[4]=0
f[5]=0 e[5]=0
f[6]=0 e[6]=0
f[7]=0 e[7]=0
f[8]=0 e[8]=0
f[9]=0 e[9]=0
1
3
44
7 79
10
4
930 063 083 184 505 278 008 109 589 2690
3 10 6 7 1 9 2 5 8
一趟收集：
3
10
1
6
2
5
8
7
505 008 109 930 063 269 278 083 184 5890
9 2 4 3 8 1 10 6 5
二趟收集：
数据结构
tjm
7
505 008 109 930 063 269 278 083 184 5890
9 2 4 3 8 1 10 6 5
二趟收集：
f[0]=0 e[0]=0
f[1]=0 e[1]=0
f[2]=0 e[2]=0
f[3]=0 e[3]=0
f[4]=0 e[4]=0
f[5]=0 e[5]=0
f[6]=0 e[6]=0
f[7]=0 e[7]=0
f[8]=0 e[8]=0
f[9]=0 e[9]=04 4
7
9
2
8
7
9
2
8
9
008 063 083 109 184 269 278 505 589 9300
3 10 2 6 8 1 7 5 4
三趟收集：
3
1
10
6
5
数据结构
tjm
10.7 各种内部排序方法的比较讨论
从时间复杂度比较
从平均时间复杂度来考虑, 直接插入排序, 冒泡排序,
直接选择排序是三种简单的排序方法, 时间复杂度都为
O(n2),而快速排序, 堆排序, 二路归并排序的时间复杂
度都为 O(nlog2n),希尔排序的复杂度介于这两者之间 。
若从最好的时间复杂度考虑, 则直接插入排序和冒泡排
序的时间复杂度最好, 为 O(n),其它的最好情形同平均
情形相同 。 若从最坏的时间复杂度考虑, 则快速排序的
为 O(n2),直接插入排序, 冒泡排序, 希尔排序同平均情
形相同, 但系数大约增加一倍, 所以运行速度将降低一
半, 最坏情形对直接选择排序, 堆排序和归并排序影响
不大 。
数据结构
tjm
从空间复杂度比较
归并排序的空间复杂度最大，为 O(n)，快速排序的空间
复杂度为 O(log2n)，其它排序的空间复杂度为 O（ 1）。
从稳定性比较
直接插入排序, 冒泡排序, 归并排序是稳定的排序
方法, 而直接选择排序, 希尔排序, 快速排序, 堆
排序是不稳定的排序方法 。
从算法简单性比较
直接插入排序、冒泡排序、直接选择排序都是简单的排
序方法，算法简单，易于理解，而希尔排序、快速排序、
堆排序、归并排序都是改进型的排序方法，算法比简单
排序要复杂得多，也难于理解。
数据结构
tjm
各种内排序方法的选择
从时间复杂度选择
对元素个数较多的排序, 可以选快速排序, 堆排序, 归
并排序, 元素个数较少时, 可以选简单的排序方法 。
从空间复杂度选择
尽量选空间复杂度为 O（ 1）的排序方法，其次选空间复
杂度为 O(log2n)的快速排序方法，最后才选空间复杂度
为 O（ n）的 2-路归并的排序方法。
数据结构
tjm
一般选择规则
（ 1） 当待排序元素的个数 n较大, 排序码分布是随机,
而对稳定性不做要求时, 则采用快速排序为宜 。
（ 2） 当待排序元素的个数 n大, 内存空间允许, 且要
求排序稳定时, 则采用 2-路归并排序为宜 。
（ 3） 当待排序元素的个数 n大, 排序码分布可能会出
现正序或逆序的情形, 且对稳定性不做要求时, 则采
用堆排序或 2-路归并排序为宜 。
（ 4） 当待排序元素的个数 n小, 元素基本有序或分布
较随机, 且要求稳定时, 则采用直接插入排序为宜 。
（ 5） 当待排序元素的个数 n小, 对稳定性不做要求时,
则采用直接选择排序为宜, 若排序码不接近逆序, 也
可以采用直接插入排序 。 冒泡排序一般很少采用 。
