知识点归并排序和基数排序ppt课件

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) / 将有序

3、的记录序列将有序的记录序列 SRi.m 和和 SRm+1.n / 归并为有序的记录序列归并为有序的记录序列 TRi.n / Mergefor (j=m+1, k=i; i=m & 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数据结构数据结构归并

4、排序的算法归并排序的算法如果记录无序序列 Rs.t 的两部分 Rs.(s+t)/2 和 R(s+t)/2+1.t分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。 由此，应该先分别对这两部分进行 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 ( RcdT

5、ype SR, RcdType &TR1, int s, int t ) / 将将SRs.t 归并排序为归并排序为 TR1s.t if (s= =t) TR1s=SRs; else / Msort 数据结构数据结构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数据

6、结构数据结构void MergeSort (SqList &L) / 对顺序表 L 作2-路归并排序 MSort(L.r, L.r, 1, L.length); / MergeSort容易看出，对 n 个记录进行归并排序的时间复杂度为(nlogn)。即： 每一趟归并的时间复杂度为 O(n)， 总共需进行 log2n 趟。数据结构数据结构10.6 基基 数数 排排 序序数据结构数据结构基数排序是一种借助“多关键字排序的思想来实现“单关键字排序的内部排序算法。多关键字的排序多关键字的排序链式基数排序链式基数排序数据结构数据结构一、多关键字的排序一、多关键字的排序 n 个记录的序列个记录的序

7、列 R1, R2, ，Rn对关键字对关键字 (Ki0, Ki1,Kid-1) 有序是指：有序是指： 其中其中: K0 : K0 被称为被称为 “最主位关键字最主位关键字Kd-1 被称为被称为 “最次位关键字最次位关键字 对于序列中任意两个记录 Ri 和 Rj(1ijn) 都满足下列(词典)有序关系： (Ki0, Ki1, ,Kid-1) (Kj0, Kj1, ,Kjd-1)数据结构数据结构 实现多关键字排序通常有两种作法:最低位优先最低位优先LSDLSD法法最高位优先最高位优先MSDMSD法法数据结构数据结构 最高位优先最高位优先MSDMSD法法: :先对先对K0K0进行排序，并按进行排序，并

8、按 K0 K0 的不同值将记录序列分成若干子序列之的不同值将记录序列分成若干子序列之后，分别对后，分别对 K1 K1 进行排序，进行排序，.， 依次类推，直至最后对最次位依次类推，直至最后对最次位关键字排序完成为止。关键字排序完成为止。最低位优先最低位优先LSDLSD法法: :先对先对 Kd-1 Kd-1 进行排序，然后对进行排序，然后对 Kd-2 Kd-2 进行排序，依次类推，直至进行排序，依次类推，直至对最主位关键字对最主位关键字 K0 K0 排序完成为止。排序完成为止。数据结构数据结构例如例如: :学生记录含三个关键字学生记录含三个关键字: :系别、班号和班内的序列号，其中以系别为最主位

9、关系别、班号和班内的序列号，其中以系别为最主位关键字。键字。 无序序列对对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的排序过程如下的排序过程如下:数据结构数据结构二、链式基数排序二、链式基数排序假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-搜集的方法，其好处是不需要进行关键字间的比较。对于数字型或字符型

10、的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-搜集的办法进行排序，称作基数排序法。数据结构数据结构例如：对下列这组关键字例如：对下列这组关键字 209, 386, 768, 185, 247, 606, 230, 834, 539 首先按其 “个位数” 取值分别为 0, 1, , 9 “分配” 成 10 组，之后按从 0 至 9 的顺序将 它们 “搜集” 在一起； 然后按其 “十位数” 取值分别为 0, 1, , 9 “分配” 成 10 组，之后再按从 0 至 9 的顺序将它们 “搜集” 在一起；最后按其“百位数重复一遍上述操作。数据结构数据结构在计算机上实

11、现基数排序时，为减少所需辅助存储空间，应采在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：用链表作存储结构，即链式基数排序，具体作法为： 待排序记录以指针相链，构成一个链表；待排序记录以指针相链，构成一个链表；“分配分配” 时，按当前时，按当前“关键字位所取值，将记录分配到不同的关键字位所取值，将记录分配到不同的 “链队列链队列” 中，每个队列中记录的中，每个队列中记录的 “关键字位关键字位” 一样；一样；“搜集时，按当前关键字位取值从小到大将各队列首尾相链搜集时，按当前关键字位取值从小到大将各队列首尾相链成一个链表成一个链表; ;对每个关键

12、字位均重复对每个关键字位均重复 2) 2) 和和 3) 3) 两步。两步。数据结构数据结构例如：p369367167239237230进行第一次分配进行第一次分配进行第一次收集进行第一次收集f0 r0f7 r7f8 r8f9 r9p230230367 167 237367167237368239369 239 数据结构数据结构进行第二次分配进行第二次分配p230237239p230367167237368239f3 r3f6 r6230 237239 367 167 368367167368进行第二次收集数据结构数据结构 进行第三次收集之后便得到记录的有序序列f1 r1p23023723936

13、7167368进行第三次分配进行第三次分配f2 r2f3 r3 167230 237 239367 368p167230237239367368数据结构数据结构 基数排序的时间复杂度为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(n

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

15、时间复杂度；对于快速排序而言，这是最坏的情况，此时的时间性能蜕化为况，此时的时间性能蜕化为O(n2)O(n2)；选择排序、堆排序和；选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。归并排序的时间性能不随记录序列中关键字的分布而改变。数据结构数据结构一、时间性能一、时间性能1. 平均的时间性能平均的时间性能基数排序基数排序时间复杂度为时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序快速排序、堆排序和归并排序时间复杂度为时间复杂度为 O(n2) O(n2)：直接插入排序、起泡排序和直接插入排序、起泡排序和简单选择排序简单选择排序时间复杂度为时间复杂度为 O(n):数

16、据结构数据结构2. 当待排记录序列按关键字顺序有序时当待排记录序列按关键字顺序有序时3. 简单选择排序、堆排序和归并排序的时间性简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。能不随记录序列中关键字的分布而改变。 直接插入排序和起泡排序能达到O(n)的时间复杂度， 快速排序的时间性能蜕化为O(n2) 。数据结构数据结构二、空间性能二、空间性能指的是排序过程中所需的辅助空间大小1. 所有的简单排序方法所有的简单排序方法(包括：直接插入、包括：直接插入、起泡和简单选择起泡和简单选择) 和堆排序的空间复杂度和堆排序的空间复杂度为为O(1)；2. 快速排序为快速排序为O(lo

17、gn)，为递归程序执行，为递归程序执行过程中，栈所需的辅助空间；过程中，栈所需的辅助空间；数据结构数据结构3. 归并排序所需辅助空间最多，其空间归并排序所需辅助空间最多，其空间复杂度为复杂度为 O(n);4. 链式基数排序需附设队列首尾指针，链式基数排序需附设队列首尾指针，则空间复杂度为则空间复杂度为 O(rd)。数据结构数据结构三、排序方法的稳定性能三、排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。 2. 当对多关键字的记录序列进行当对多关键字的记录序列进行LSD方方法排法排序时，必须采用稳定的排序方法。

18、序时，必须采用稳定的排序方法。数据结构数据结构例如：例如： 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 )若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 )则称该排序方法是稳定的;若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 )则称该排序方法是不稳定的。数据结构数据结构 3. 对于不稳定的排序方法，只要能举出对于不稳定的排序方法，只要能举出一个实例说明即可。一个实例说明即可。 4. 直接选择排序、快速排序、堆排序和希尔直接选择排序、快速排序、堆排序和希尔排序是不稳定的排序方法。排序是不稳定的排序方法。例如例如 : 对对 4, 3, 4, 2 进行快速排序，进行快速排序， 得到得到 2, 3, 4, 4 数据结构数据结构讨论：直接选择排序是否稳定？讨论：直接选择排序是否稳定？例如例如 : 对序列对序列5 ，8， 5， 2， 9 进行直接选进行直接选择排序得到择排序得到 2 ，8， 5， 5 ， 9不稳定不稳定数据结构数据结构排序排序 插入排序直插排序、折半排序、希尔排序）插入排序直插排序、折半排序、希尔排序） 交换排序冒泡排序、快速排序）交换排序冒泡排序、快