数据结构 10内部排序C.ppt

更 正： 第9章 内部排序 1. 什么是“多关键字”排序？实现方法？ 多关键字排序的实现方法通常有两种： 9.6 基数排序 (Radix Sort) 2. 单逻辑关键字怎样“按位值”排序？ 讨论：是借用MSD方式来排序呢，还是借用LSD方式？ 计算机怎样实现LSD算法？ 这种LSD排序方法称为： 讨论：所用队列是顺序结构，浪费空间，能否改用链式结构？ 例: 第一趟收集的结果： 第二趟收集的结果： 如何编程实现？ 一趟“分配”过程的算法流程 链表基数排序的算法： 基数排序算法分析 各种内部排序方法的比较 (教材P289） 讨论：若初始记录基本有序，则选用哪些排序方法比较适合？若初始记录基本无序，则最好选用哪些排序方法？ * ① 教材278页倒数第7行有误：完全二叉树的深度不是 ? log2n?+1 ，而应该是? log2n ? +1 ，倒6行错误相同； ②教材291页第二段中的非终端结点元素位置＝?n/2? 完全正确！ 两个结论： 完全二叉树的叶子数＝? n/2?，取上限； 但完全二叉树的最后一个非终端结点位置＝?n/2? ，应取下限！ 9.1 概述 9.2 插入排序 9.3 交换排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 附：各种内部排序方法的比较 例1：对一副扑克牌该如何排序？ 若规定花色和面值的顺序关系为： 花色： ? ? ? ? ? ? ? 面值：2 3 4 5 6 7 8 9 10 J Q K A 则可以先按花色排序，花色相同者再按面值排序； 也可以先按面值排序，面值相同者再按花色排序。 例2：职工分房该如何排序？ 华工规定：先以总分排序（职称分＋工龄分）； 总分相同者，再按配偶总分排序，其次按配偶职称、工龄、人口……等等排序。 以上两例都是典型的多关键字排序！ 最高位优先法MSD (Most Significant Digit first) 例：对一副扑克牌该如何排序？ 答：若规定花色为第一关键字（高位），面值为第二关键字（低位），则使用MSD和LSD方法都可以达到排序目的。 MSD方法的思路：先设立4个花色“箱”，将全部牌按花色分别归入4个箱内（每个箱中有13张牌）；然后对每个箱中的牌按面值进行插入排序（或其它稳定算法）。 LSD方法的思路：先按面值分成13堆（每堆4张牌），然后对每堆中的牌按花色进行排序（用插入排序等稳定的算法）。 想一想：用哪种方法更快些？ 最低位优先法LSD (Least Significant Digit first) 要讨论的问题： 1. 什么是“多关键字”排序？实现方法？ 2. 单逻辑关键字怎样“按位值”排序？ 基数排序的基本思想是： 借助多关键字排序的思想对单逻辑关键字进行排序。即：用关键字不同的位值进行排序。 设n 个记录的序列为：{V0, V1, …, Vn-1 }，可以把每个记录Vi 的单关键码 Ki 看成是一个d元组（Ki1, Ki2, …, Kid），则其中的每一个分量Kij ( 1? j ? d ) 也可看成是一个关键字。 4 注1： Ki1＝最高位，Kid＝最低位；Ki共有d位，可看成d元组； 注2： 每个分量Kij (1 ? j ? d ) 有radix种取值，则称radix为基数。 26 (9, 8, 4) (0, 1, …, 9) （a, b, …, z） (d, i, a, n) 3 10 例1：关键码984可以看成是 元组；基数radix 为 。 例2：关键码dian可以看成是 元组；基数radix 为 。 思路： 因为有分组，故此算法需递归实现。 例：初始关键字序列T=（32, 13, 27, 32*, 19，33），请分别用MSD和LSD进行排序，并讨论其优缺点。 法1（MSD）：原始序列：32, 13, 27, 32*, 19， 33 先按高位Ki1 排序：（13, 19）, 27, （32, 32*，33） 再按低位Ki2 排序 ： 13, 19 ， 27, 32, 32*, 33 法2（LSD）： 原始序列： 32, 13, 27, 32*, 19 ，33 先按低位Ki2排序： 32, 32*, 13, 33, 27, 19 再按高位Ki1排序： 13, 19 , 27, 32, 32*, 33 无需分组，易编程实现！ 例：T=（02，77，70，54，64，21，55，11），用LSD排序。 分析： ①各