知识点归并排序与基数排序

1、数据结构数据结构10.5 归归 并并 排排 序（知识点三）序（知识点三）数据结构数据结构 归并的含义是将两个或两个以上的有序表组合成一个新的有序表。 归并排序可分为两路归并排序,或多路归并排序，既可用于内排序，也可用于外排序。这里仅对内排序的两路归并方法进行讨论。数据结构数据结构两路归并排序算法思路：两路归并排序算法思路：假设初始序列含有个记录，首先把个记录看成个长度为的有序序列，进行两两归并，得到 个长度为的关键字有序序列，再两两归并直到所有记录归并成一个长度为的有序序列为止。数据结构数据结构在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻位置相邻的记录有序子序列归并为一个记录的

2、有序序列。有有 序序 序序 列列 ri.n有序子序列有序子序列 ri.m有序子序列有序子序列 rm+1.n这个操作对顺序表而言，是轻而易举的。数据结构数据结构例：已知关键字序列：例：已知关键字序列： 46,55,13,4246,55,13,42 归并排序过程如下：归并排序过程如下： 46 5513 42数据结构数据结构void merge (rcdtype sr, rcdtype &tr, int i, int m, int n) / 将有序的记录序列 sri.m 和 srm+1.n / 归并为有序的记录序列 tri.n / mergefor (j=m+1, k=i; i=m &

3、; j=n; +k) / 将将sr中记录由小到大地并入中记录由小到大地并入tr if (sri.key=srj.key) trk = sri+; else trk = srj+; 数据结构数据结构if (i=m) trk.n = sri.m; / 将剩余的 sri.m 复制到 trif (j=n) trk.n = srj.n; / 将剩余的 srj.n 复制到 tr数据结构数据结构归并排序的算法归并排序的算法如果记录无序序列 rs.t 的两部分 rs. (s+t)/2 和 r (s+t)/2 +1.t分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。 由此，应该

4、先分别对这两部分进行 2-路归并排序。数据结构数据结构例如：例如：52, 23, 80, 36, 68, 14 (s=1, t=6) 52, 23, 80 36, 68, 14 52, 2380 52 23, 52 23, 52, 8036, 6814366836, 6814, 36, 68 14, 23, 36, 52, 68, 80 23数据结构数据结构void msort ( rcdtype sr, rcdtype &tr1, int s, int t ) / 将srs.t 归并排序为 tr1s.t if (s= =t) tr1s=srs; else / msort 数据结构数据

5、结构m = (s+t)/2; / 将srs.t平分为srs.m和srm+1.tmsort (sr, tr2, s, m); / 递归地将srs.m归并为有序的tr2s.mmsort (sr, tr2, m+1, t); /递归地srm+1.t归并为有序的tr2m+1.tmerge (tr2, tr1, s, m, t); / 将tr2s.m和tr2m+1.t归并到tr1s.t数据结构数据结构void mergesort (sqlist &l) / 对顺序表 l 作2-路归并排序 msort(l.r, l.r, 1, l.length); / mergesort容易看出，对 n 个记录进

6、行归并排序的时间复杂度为(nlogn)。即： 每一趟归并的时间复杂度为 o(n)， 总共需进行 log2n 趟。数据结构数据结构10.6 基基 数数 排排 序序数据结构数据结构基数排序基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。多关键字的排序多关键字的排序链式基数排序链式基数排序数据结构数据结构一、多关键字的排序一、多关键字的排序 n 个记录的序列个记录的序列 r1, r2, ，rn对关键字对关键字 (ki0, ki1, ,kid-1) ) 有序有序是指： 其中其中: : k0 被称为被称为 “最主最主”位关键字位关键字kd-1 被称为被称为 “最次最次”位关

7、键字位关键字 对于序列中任意两个记录 ri 和 rj(1ijn) 都满足满足下列(词典词典)有序有序关系： (ki0, ki1, , ,kid-1) ) (kj0, kj1, , ,kjd-1) )数据结构数据结构 实现多关键字排序通常有两种作法:最低位优先最低位优先lsd法法最高位优先最高位优先msd法数据结构数据结构 最高位优先最高位优先msdmsd法:先对先对k0进行排序进行排序，并按 k0 的不同值将记录序列分成若干子序列若干子序列之后，分别对 k1 进行排序，.， 依次类推，直至最后对最次位关直至最后对最次位关键字排序完成为止键字排序完成为止。最低位优先最低位优先lsdlsd法法:

8、:先对 kd-1 进行排序，然后对 kd-2 进行排序，依次类推，直至对最直至对最主位关键字主位关键字 k0 排序完成为止排序完成为止。数据结构数据结构例如例如: :学生记录含三个关键字:系别系别、班号班号和班内的序列号班内的序列号，其中以系别为最主位关键字。 无序序列无序序列对对k2排序排序对对k1排序排序对对k0排序排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30lsd的排序过程如下:数据结构数

9、据结构二、链式基数排序二、链式基数排序假如多关键字的记录序列中，每个关键字的取值范围相同，则按lsd法进行排序时，可以采用“分配分配- -收集收集”的方法，其好处是不需要进行关键字间的比较。对于数字型或字符型的单关键字单关键字，可以看成看成是由多个数位或多个字符构成的多关键字多关键字，此时可以采用采用这种“分配分配- -收集收集”的办法进行排序进行排序，称作基数排序法称作基数排序法。数据结构数据结构例如：例如：对下列这组关键字 209, 386, 768, 185, 247, 606, 230, 834, 539 首先按其 “个位数” 取值分别为 0, 1, , 9 “分配分配” 成 10 组

10、，之后按从 0 至 9 的顺序将 它们 “收集收集” 在一起； 然后按其 “十位数” 取值分别为 0, 1, , 9 “分配分配” 成 10 组，之后再按从 0 至 9 的顺序将它们 “收集收集” ” 在一起；最后按其“百位数”重复一遍上述操作。数据结构数据结构在计算机上实现基数排序时，为减少所需辅助存储空间，应采在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构用链表作存储结构，即链式基数排序，具体作法为：，即链式基数排序，具体作法为： 待排序记录以指针相链，构成一个链表；待排序记录以指针相链，构成一个链表；“分配分配” ” 时，按当前时，按当前“关键字位关键字位”所取值

11、，将记录分配到不同所取值，将记录分配到不同的的 “ “链队列链队列” ” 中，每个队列中记录的中，每个队列中记录的 “ “关键字位关键字位” ” 相同；相同；“收集收集”时，按当前关键字位取值从小到大时，按当前关键字位取值从小到大将各队列首尾相链将各队列首尾相链成一个链表成一个链表; ;对每个关键字位均重复对每个关键字位均重复 2) 和和 3) 两步。两步。数据结构数据结构例如：p369367167239237138230139进行第一次分配进行第一次分配进行第一次收集进行第一次收集f0 r0f7 r7f8 r8f9 r9p230230367 167 237367167237138 36823

12、9139369 239 139138数据结构数据结构进行第二次分配进行第二次分配p230237138239139p230367167237138368239139f3 r3f6 r6230 237138239 139367 167 368367167368进行第二次收集数据结构数据结构 进行第三次收集之后便得到记录的有序序列进行第三次收集之后便得到记录的有序序列f1 r1p230237138239139367167368进行第三次分配进行第三次分配f2 r2f3 r3138 139 167230 237 239367 368p138139167230237239367368数据结构数据结构 基

13、数排序的时间复杂度为基数排序的时间复杂度为o(d(n+rd)其中：分配为o(n) （n个数） 收集为o(rd)(rd为“基”) d为“分配-收集”的趟数（d位）数据结构数据结构10.7 各种排序方法的综合比较各种排序方法的综合比较数据结构数据结构排序方法排序方法平均情况平均情况最好情况最好情况最坏情况最坏情况直 接 插 入 排 序直 接 插 入 排 序o(n2)o(n)o(n2)希尔排序希尔排序o(nlog2n)o(n1.3)o(n2)冒泡排序冒泡排序o(n2)o (n)o(n2)快速排序快速排序o(nlog2n)o(nlog2n)o(n2)简 单 选 择 排 序简 单 选 择 排 序o(n2

14、)o(n2)o(n2)堆排序堆排序o(nlog2n)o(nlog2n)o (nlog2n)归并排序归并排序o(nlog2n)o(nlog2n)o(nlog2n)数据结构数据结构数据结构数据结构数据结构数据结构数据结构数据结构数据结构数据结构数据结构数据结构关键码的分布情况比较关键码的分布情况比较当待排序记录按关键码有序时，插入排序和冒泡排序能达当待排序记录按关键码有序时，插入排序和冒泡排序能达到到o( (n) )的时间复杂度；对于快速排序而言，这是最坏的的时间复杂度；对于快速排序而言，这是最坏的情况，此时的时间性能蜕化为情况，此时的时间性能蜕化为o( (n2) )；选择排序、堆排序；选择排序、

15、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改和归并排序的时间性能不随记录序列中关键字的分布而改变。变。数据结构数据结构一、时间性能一、时间性能1. 平均的时间性能平均的时间性能基数排序基数排序时间复杂度为时间复杂度为 o(nlogn)：快速排序、堆排序和归并排序快速排序、堆排序和归并排序时间复杂度为时间复杂度为 o(n2)：直接插入排序、起泡排序和直接插入排序、起泡排序和简单选择排序简单选择排序时间复杂度为时间复杂度为 o(n):数据结构数据结构2. 当待排记录序列按关键字顺序有序时当待排记录序列按关键字顺序有序时3. 简单选择排序、堆排序和归并排序简单选择排序、堆排序和归并排序的

16、时间性能不随不随记录序列中关键字的分布而改变。 直接插入排序直接插入排序和起泡排序起泡排序能达到o(n)的时间复杂度， 快速排序快速排序的时间性能蜕化为o(n2) 。数据结构数据结构二、空间性能二、空间性能指的是排序过程中所需的辅助空间大小1. 所有的简单排序方法简单排序方法(包括：直接插入、起泡和简单选择) 和堆排序堆排序的空间复杂度为为o(1)；2. 快速排序为快速排序为o(logn)，为递归程序执行过程中，栈所需的辅助空间；数据结构数据结构3. 归并排序归并排序所需辅助空间最多，其空间复杂度为 o(n);4. 链式基数排序链式基数排序需附设队列首尾指针，则空间复杂度为 o(rd)。数据结

17、构数据结构三、排序方法的稳定性能三、排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。 2. 当对多关键字的记录序列进行lsd方法排序时，必须采用稳定的排序方法。数据结构数据结构例如例如： 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 )若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 )则称该排序方法是稳定稳定的;若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 )则称该排序方法是不稳定不稳定的。数据结构数据结构

18、3. 对于不稳定的排序方法，只要能举出一个实例说明即可。 4. 直接选择排序、直接选择排序、快速排序、堆排序和希尔快速排序、堆排序和希尔排序是不稳定的排序方法排序是不稳定的排序方法。例如例如 : 对 4, 3, 4, 2 进行快速排序， 得到 2, 3, 4, 4 数据结构数据结构讨论：直接选择排序是否稳定？讨论：直接选择排序是否稳定？例如例如 : 对序列5 ，8， 5， 2， 9 进行直接选择排序得到 2 ，8， 5， 5 ， 9不稳定不稳定数据结构数据结构排序排序 插入排序（直插排序、折半排序、插入排序（直插排序、折半排序、希尔排序希尔排序） 交换排序（冒泡排序、交换排序（冒泡排序、快速排序快速排序） 选择排序（直选排序、选择排序（直选排序、堆排序堆排序） 归并排序（二路归并排序）归并排序（二路归并排序） 基数排序基数排序 （多关键字排序、基数排序）（多关键字排序、基数排序）本章小结本章小结数据结构数据结构 1. 了解排序的定义定义和各种排序方法的特点。熟悉各种方法的排序过程及其依据的原则方法的排序过程及其依据的原则。基于“关键字间的比较关键字间的比较”进行排序的方法可以按排序