《数据结构》 第十章内部排序（下）
《数据结构》 第十章 内部排序 (下)
数据结构 10.5归并排序 归并—将两个或两个以上的有序表组合成一个新的 有序表。 多路归并排序：将三个或三个以上有序子区间合并成 一个有序子区间的排序，称为多路归并排序。常见的 有三路归并排序、四路归并排序等，具体实现的方法 与二路归并排序类似。 2-路归并排序 排序过程：设初始序列含有个记录，则可看成n个有 序的子序列，每个子序列长度为1。 两两合并，得到n/2+1个长度为2或1的有序子序列。 再两两合并，.如此重复，直至得到一个长度为n 的有序序列为止。 算法参见P283,P284 m
数据结构 tjm 10.5 归并排序 归并——将两个或两个以上的有序表组合成一个新的 有序表。 多路归并排序：将三个或三个以上有序子区间合并成 一个有序子区间的排序，称为多路归并排序。常见的 有三路归并排序、四路归并排序等，具体实现的方法 与二路归并排序类似。 算法参见P283, P284 2-路归并排序 排序过程：设初始序列含有n个记录，则可看成n个有 序的子序列，每个子序列长度为1。 两两合并，得到n/2＋1个长度为2或1的有序子序列。 再两两合并，.如此重复，直至得到一个长度为n 的有序序列为止
数据结构 例： 初始关键字：[438][65]97]76]13][27] 一趟归并后：384916597列][1376]27] 二趟归并后：384965 97][132776] 三趟归并后：[13 2738 49657697] 算法评价 时间复杂度：T(n)=0(nlog2n) 空间复杂度：S()=0() tjm
数据结构 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)
数据结构 10.6基数排序 10.6.1多关键字排序 多关键字排序定义： 在实际应用中，有时的排序会需要按几种不同排序码 来排序。 对于多关键字排序（假设有d个关键字)，则可以按 第1、2、.、d个关键字的顺序排序，也可以按第d、 d-1、d-2、.、2、1个关键字的顺序排序。 例：对52张扑克牌按以下次序排序： 2<3<.<A<◆2<◆3<.<◆A< 2<3<.<9A<◆2<3<.<◆A 两个关键字：花色（<◆<<◆) 面值（2<3<.<A) 并且“花色”地位高于“面值
数据结构 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个关键字的顺序排序
数据结构 多关键字排序方法 最高位优先法(MSD):先对最高位关键字k1(如花色) 排序，将序列分成若干子序列，每个子序列有相同的k 值；然后让每个子序列对次关键字k,（如面值)排序， 又分成若干更小的子序列；依次重复，直至就每个子序 列对最低位关键字k排序；最后将所有子序列依次连接 在一起成为一个有序序列。 最低位优先法(LSD):从最低位关键字k起进行排序， 然后再对高一位的关键字排序，.依次重复，直至对 最高位关键字k排序后，便成为一个有序序列。 MSD与LSD不同特点： 按MSD排序，必须将序列逐层分割成若干子序列， 然后对各子序列分别排序。 按LSD排序，不必分成子序列，对每个关键字都是 整个序列参加排序；并且可不通过关键字比较，而 通过若干次分配与收集实现排序
数据结构 tjm 最高位优先法（MSD)：先对最高位关键字k1（如花色） 排序，将序列分成若干子序列，每个子序列有相同的k1 值；然后让每个子序列对次关键字k2（如面值）排序， 又分成若干更小的子序列；依次重复，直至就每个子序 列对最低位关键字kd排序；最后将所有子序列依次连接 在一起成为一个有序序列。 最低位优先法(LSD)：从最低位关键字kd起进行排序， 然后再对高一位的关键字排序，.依次重复，直至对 最高位关键字k1排序后，便成为一个有序序列。 MSD与LSD不同特点： 按MSD排序，必须将序列逐层分割成若干子序列， 然后对各子序列分别排序。 按LSD排序，不必分成子序列，对每个关键字都是 整个序列参加排序；并且可不通过关键字比较，而 通过若干次分配与收集实现排序。 多关键字排序方法