第10章 排序
数据结构讲义
- 归并与基数排序
归并排序
归并——将两个或两个以上的有序表组合成一个新的有序表，叫~
2-路归并排序
设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。
两两合并，得到n/2个长度为2或1的有序子序列。
再两两合并，……如此重复，直至得到一个长度为n的有序序列为止。
例子：合并两个有序表
顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。
0 1 2 3 4
49
13
65
97
76
7
80
A
B
0 1 2 3 4 5 6 7
C
i
j
k
0 1 2 3 4
49
13
65
97
76
7
80
A
B
0 1 2 3 4 5 6 7
C
i
j
k
7
0 1 2 3 4
49
13
65
97
76
7
80
A
B
0 1 2 3 4 5 6 7
C
i
j
k
7
0 1 2 3 4
49
13
65
97
76
7
80
A
B
0 1 2 3 4 5 6 7
C
i
j
k
7
13
0 1 2 3 4
49
13
65
97
76
7
80
A
B
0 1 2 3 4 5 6 7
C
i
j
k
7
13
49
0 1 2 3 4
49
13
65
97
76
7
80
A
B
0 1 2 3 4 5 6 7
C
i
j
k
7
13
49
0 1 2 3 4
49
13
65
97
76
7
80
A
B
0 1 2 3 4 5 6 7
C
i
j
k
7
13
49
65
0 1 2 3 4
49
13
65
97
76
7
80
A
B
0 1 2 3 4 5 6 7
C
i
j
k
7
13
49
65
0 1 2 3 4
49
13
65
97
76
7
80
A
B
0 1 2 3 4 5 6 7
C
i
j
k
7
13
49
65
76
0 1 2 3 4
49
13
65
97
76
7
80
A
B
0 1 2 3 4 5 6 7
C
i
j
k
7
13
49
65
76
0 1 2 3 4
49
13
65
97
76
7
80
A
B
0 1 2 3 4 5 6 7
C
i
j
k
7
13
49
65
76
80
0 1 2 3 4
49
13
65
97
76
7
80
A
B
0 1 2 3 4 5 6 7
C
i
j
k
7
13
49
65
76
80
0 1 2 3 4
49
13
65
97
76
7
80
A
B
0 1 2 3 4 5 6 7
C
i
j
k
7
13
49
65
76
80
至此 B 表的元素都已移入 C 表，只需将 A 表的剩余部分移入 C 表即可。
0 1 2 3 4
49
13
65
97
76
7
80
A
B
0 1 2 3 4 5 6 7
C
i
j
k
7
13
49
65
76
80
至此 B 表的元素都已移入 C 表，只需将 A 表的剩余部分移入 C 表即可。
97
例子：归并排序
初始关键字： [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(nlogn)
空间复杂度：
S(n)=O(n)
它是一个稳定的排序方法。
基数排序
多关键字排序
例 对52张扑克牌按以下次序排序：
2<3<……<A<2<3<……<A<
2<3<……<A<2<3<……<A
两个关键字：花色（ <<< ）
面值（2<3<……<A）
并且“花色”地位高于“面值”
多关键字排序方法
最高位优先法（MSD)：先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列。
最低位优先法(LSD)：从最低位关键字kd起进行排序，然后再对高一位的关键字排序，……依次重复，直至对最高位关键字k1排序后，便成为一个有序序列。
MSD与LSD不同特点
按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序。
按LSD排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序。
链式基数排序
基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法。
链式基数排序：用链表作存储结构的基数排序。
基数排序的演示
例
初始状态：
278
109
063
930
589
184
505
269
008
083
109
589
269
278
063
930
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
一趟收集：
505
008
109
930
063
269
278
083
184
589
二趟收集：
083
184
589
063
505
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
一趟收集：
008
063
083
109
184
269
278
505
589
930
三趟收集：
109
008
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
二趟收集：
链式基数排序步骤
设置10个队列，f[i]和e[i]分别为第i个队列的头指针和尾指针。
第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同。
第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表。
重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列。
算法评价
时间复杂度：
分配：T(n)=O(n)
收集：T(n)=O(rd)、
T(n)=O(d(n+rd))
其中：n——记录数， d——关键字数， rd——关键字取值范围(如十进制为10) 。
空间复杂度：
S(n)=2rd个队列指针+n个指针域空间。
排序算法小结
平均时间 最差 最佳 辅助空间 稳定性
直接插入 O(n2) O(n2) O(n) O(1) 稳定
起泡排序 O(n2) O(n2) O(n) O(1) 稳定
直接选择 O(n2) O(n2) O(n2) O(1) 不稳定
希尔排序 O() O(1) 不稳定
快速排序 O(nlog2n) O(n2) 同平均 O(log2n) 不稳定
堆排序 O(nlog2n) 同平均 同平均 O(1) 不稳定
归并排序 O(nlog2n) 同平均 同平均 O(n) 稳定
基数排序 O(d(n+r)) 同平均 同平均 O(n+r) 稳定
作业
若一组记录的关键码为（46, 79, 56, 38, 40, 84），写出二路归并排序和链式基数排序一趟排序的结果。
