《数据结构》 第十章下)
《数据结构》 第十章(下)
数据结构 105归并排序 归并—将两个或两个以上的有序表组合成一个新的 有序表 多路归并排序:将三个或三个以上有序子区间合并成 个有序子区间的排序,称为多路归并排序。常见的 有三路归并排序、四路归并排序等,具体实现的方法 与二路归并排序类似 2-路归并排序 排序过程:设初始序列含有n个记录,则可看成n个有 序的子序列,每个子序列长度为1 两两合并,得到n/2+1个长度为2或1的有序子序列。 再两两合并,…如此重复,直至得到一个长度为n 的有序序列为止 算法参见P283,P284
数据结构 tjm 10.5 归并排序 归并——将两个或两个以上的有序表组合成一个新的 有序表。 多路归并排序：将三个或三个以上有序子区间合并成 一个有序子区间的排序，称为多路归并排序。常见的 有三路归并排序、四路归并排序等，具体实现的方法 与二路归并排序类似。 算法参见P283, P284 2-路归并排序 排序过程：设初始序列含有n个记录，则可看成n个有 序的子序列，每个子序列长度为1。 两两合并，得到n/2＋1个长度为2或1的有序子序列。 再两两合并，……如此重复，直至得到一个长度为n 的有序序列为止
数据结构 例: 初始关键字:4938165197[76|3[27 趙归并后:384916597][376[27] 二趟归并后:|38496597[132776 三趟归并后:13273849657697 算法评价 时间复杂度:T(n)=0nlog2n) 空间复杂度:S(m)=O(m)
数据结构 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.61多关键排序 多关键字排序定义: 在实际应用中,有时的排序会需要按几种不同排序码 来排序。 对于多关键字排序(假设有d个关键字),则可以按 第1、2、…、d个关键字的顺序排序,也可以按第d、 d-1、d-2、…、2、1个关键字的顺序排序。 例:对52张扑克牌按以下次序排序: 23<A<◆2<◆3<<◆A< v2<3<<A<命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(如花色) 排序,将序列分成若干子序列,每个子序列有相同的k1 值;然后让每个子序列对次关键字k2(如面值)排序, 又分成若干更小的子序列;依次重复,直至就每个子序 列对最低位关键字k排序;最后将所有子序列依次连接 在一起成为一个有序序列。 最低位优先法LSD):从最低位关键字k起进行排序, 然后再对高一位的关键字排序 依次重复,直至对 最高位关键字k排序后,便成为一个有序序列 MSD与LSD不同特点: 按MSD排序,必须将序列逐层分割成若干子序列, 然后对各子序列分别排序。 按LSD排序,不必分成子序列,对每个关键字都是 整个序列参加排序;并且可不通过关键字比较,而 通过若干次分配与收集实现排序
数据结构 tjm 最高位优先法（MSD)：先对最高位关键字k1（如花色） 排序，将序列分成若干子序列，每个子序列有相同的k1 值；然后让每个子序列对次关键字k2（如面值）排序， 又分成若干更小的子序列；依次重复，直至就每个子序 列对最低位关键字kd排序；最后将所有子序列依次连接 在一起成为一个有序序列。 最低位优先法(LSD)：从最低位关键字kd起进行排序， 然后再对高一位的关键字排序，……依次重复，直至对 最高位关键字k1排序后，便成为一个有序序列。 MSD与LSD不同特点： 按MSD排序，必须将序列逐层分割成若干子序列， 然后对各子序列分别排序。 按LSD排序，不必分成子序列，对每个关键字都是 整个序列参加排序；并且可不通过关键字比较，而 通过若干次分配与收集实现排序。 多关键字排序方法
数据结构 10.62链式基数排序 基数排序:借助“分配”和“收集”对单逻辑关键字进 行排序的一种方法。 链式基数排序:用链表作存储结构的基数排序。 链式基数排序步骤: 设置10个队列,f和e分别为第个队列的头指针和尾 指针。 第一趟分配对最低位关键字(个位)进行,将链表中记 录分配至10个链队列中,每个队列记录的关键字的个位 相同。 第一趟收集是改变所有非空队列的队尾记录的指针域, 令其指向下一个非空队列的队头记录,重新将10个队列 链成一个链表。 重复上述两步,进行第二趟、第三趟分配和收集,分别 对十位、百位进行,最后得到一个有序序列
数据结构 tjm 10.6.2 链式基数排序 基数排序：借助“分配”和“收集”对单逻辑关键字进 行排序的一种方法。 链式基数排序：用链表作存储结构的基数排序。 链式基数排序步骤： 设置10个队列，f[i]和e[i]分别为第i个队列的头指针和尾 指针。 第一趟分配对最低位关键字（个位）进行，将链表中记 录分配至10个链队列中，每个队列记录的关键字的个位 相同。 第一趟收集是改变所有非空队列的队尾记录的指针域， 令其指向下一个非空队列的队头记录，重新将10个队列 链成一个链表。 重复上述两步，进行第二趟、第三趟分配和收集，分别 对十位、百位进行，最后得到一个有序序列
例 数据结构 初始状态: 278109063930589184505269008083 e0 el e2 e3 el4 5le6]e[7e8]e9 269 083 008589 930 063184505 278109 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 趟收集: 930063083184505278008109589269
数据结构 tjm 例： 初始状态： 278 109 063 930 589 184 505 269 008 083 109 589 269 930 063 278 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 一趟收集：
数据结构 趟收集: 930063083184—505-2780081091589+269 e[ol ell e[2 e[| el4 e[5] e[61 e[7 el8 e[9l 109 589 008 269 184 配|505 930 063278083 f0 f1 f2 f3 f4 f5 f6 f7 f8 f91 趟收集: 505008 099300632692780831184-589
数据结构 tjm 505 008 109 930 063 269 278 083 184 589 二趟收集： 083 184 589 505 063 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 一趟收集：
数据结构 趟收集 505008109930063269278083184589 e|0e[1e2e3e|4]e5e|6]e[7e8]e9 083 趟|063184278 589 008109269 505 930 n10m1f2]f3n4f5f67]f8]f9 趟收集: 008063083109184269278505589930
数据结构 tjm 008 063 083 109 184 269 278 505 589 930 三趟收集： 008 109 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 二趟收集：
数据结构 算法参见P288 算法评价 分配:T(n)=O(m 收集:T(n)=O(rd) 时间复杂度:T(n)=O(d(n+rd) 其中:n记录数 d关键字数 rd-—关键字取值范围 空间复杂度:S(n)=2rd个队列指针+n个指针域空 间故它的空间复杂度为0(rd)。 由于基数排序中值相同的元素的相对位置在分配 和收集中,不会发生变化,所以基数排序是一种 稳定的排序方法
数据结构 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)。 由于基数排序中值相同的元素的相对位置在分配 和收集中，不会发生变化，所以基数排序是一种 稳定的排序方法