《数据结构》课程PPT教学课件（2015）第10章 内部排序（下）

《数据结构》 第十章内部排序（下）

《数据结构》 第十章 内部排序 (下)

数据结构 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排序，不必分成子序列，对每个关键字都是 整个序列参加排序；并且可不通过关键字比较，而 通过若干次分配与收集实现排序。 多关键字排序方法

数据结构 10.6.2链式基数排序 基数排序：借助“分配”和“收集”对单逻辑关键字进 行排序的一种方法。 链式基数排序：用链表作存储结构的基数排序。 链式基数排序步骤： 设置10个队列，f)和e[分别为第个队列的头指针和尾 指针。 第一趟分配对最低位关键字（个位）进行，将链表中记 录分配至10个链队列中，每个队列记录的关键字的个位 相同。 第一趟收集是改变所有非空队列的队尾记录的指针域， 令其指向下一个非空队列的队头记录，重新将10个队列 链成一个链表。 重复上述两步，进行第二趟、第三趟分配和收集，分别 对十位、百位进行，最后得到一个有序序列

数据结构 tjm 10.6.2 链式基数排序 基数排序：借助“分配”和“收集”对单逻辑关键字进 行排序的一种方法。 链式基数排序：用链表作存储结构的基数排序。 链式基数排序步骤： 设置10个队列，f[i]和e[i]分别为第i个队列的头指针和尾 指针。 第一趟分配对最低位关键字（个位）进行，将链表中记 录分配至10个链队列中，每个队列记录的关键字的个位 相同。 第一趟收集是改变所有非空队列的队尾记录的指针域， 令其指向下一个非空队列的队头记录，重新将10个队列 链成一个链表。 重复上述两步，进行第二趟、第三趟分配和收集，分别 对十位、百位进行，最后得到一个有序序列

例： 数据结构 初始状态： 278 109 063 930 589 184 505 269 008 083 e0] e e2] e[3] e[4] e e[6] e7] e[8 分配 083 930 063 184 505 f0] f川 f2] f3] fT4] f f6] f7] q8j 趟收集： 930 063 083184505278008109 589→269

数据结构 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 一趟收集：

数据结构 趟收集： 930 063 083 184 505→ 278→ 008 109→ 589→ 269 e[O] e1] e[2]e3] e[4 e[5] e61 e[7] e[8] e9] 109 589 趟 008 269 184 505 930 063 278 083 f0] 2] f3] f4] f6] f7] f8] f9] 趟收集： 505 008→109930063269 278083184 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 一趟收集：

数据结构 趟收集： 505 008 109 930 063 269 278 083 184 589 e[0] e山 e2] e3] e[4] e5] e[6] e7] e[8] e[9] 083 趟 589 278 配 269 505 930 f0] f1] f2] f3] f4] f f6] f71 f8] f] 三趟收集： 008 063 083 109→184→ 269 +278 505 589 93Q

数据结构 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() 收集：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)。 由于基数排序中值相同的元素的相对位置在分配 和收集中，不会发生变化，所以基数排序是一种 稳定的排序方法