《第9章内部排序第9章内部排序C》由会员分享，可在线阅读，更多相关《第9章内部排序第9章内部排序C（21页珍藏版）》请在金锄头文库上搜索。
1、1,更 正：, 教材278页倒数第7行有误：完全二叉树的深度不是 log2n+1 ，而应该是 log2n +1 ，倒6行错误相同； 教材291页第二段中的非终端结点元素位置n/2 完全正确！ 两个结论： 完全二叉树的叶子数 n/2，取上限； 但完全二叉树的最后一个非终端结点位置n/2 ，应取下限！,2,9.1 概述 9.2 插入排序 9.3 交换排序 9.4 选择排序 9.5 归并排序 9.6 基数排序,第9章 内部排序,附：各种内部排序方法的比较,3,9.6 基数排序 (Radix Sort),要讨论的问题： 1. 什么是“多关键字”排序？实现方法？ 2. 单逻辑关键字怎样“按位值”排序？,
2、基数排序的基本思想是：,借助多关键字排序的思想对单逻辑关键字进行排序。即：用关键字不同的位值进行排序。,4,1. 什么是“多关键字”排序？实现方法？,例1：对一副扑克牌该如何排序？ 若规定花色和面值的顺序关系为： 花色： 面值：2 3 4 5 6 7 8 9 10 J Q K A 则可以先按花色排序，花色相同者再按面值排序； 也可以先按面值排序，面值相同者再按花色排序。,例2：职工分房该如何排序？ 华工规定：先以总分排序（职称分工龄分）； 总分相同者，再按配偶总分排序，其次按配偶职称、工龄、人口等等排序。,以上两例都是典型的多关键字排序！,5,多关键字排序的实现方法通常有两种：,最高位优先法M
3、SD (Most Significant Digit first),例：对一副扑克牌该如何排序？ 答：若规定花色为第一关键字（高位），面值为第二关键字（低位），则使用MSD和LSD方法都可以达到排序目的。 MSD方法的思路：先设立4个花色“箱”，将全部牌按花色分别归入4个箱内（每个箱中有13张牌）；然后对每个箱中的牌按面值进行插入排序（或其它稳定算法）。 LSD方法的思路：先按面值分成13堆（每堆4张牌），然后对每堆中的牌按花色进行排序（用插入排序等稳定的算法）。,想一想：用哪种方法更快些？,最低位优先法LSD (Least Significant Digit first),6,2. 单逻辑关
4、键字怎样“按位值”排序？,设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,思路：,7,因为有分组，故此算法需递归实现。,讨论：是借用MSD方式来排序呢，还是借用LSD方
5、式？,例：初始关键字序列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,无需分组，易编程实现！,8
6、,例：T=（02，77，70，54，64，21，55，11），用LSD排序。 分析： 各关键字可视为2元组；每位的取值范围是：0-9；即基数radix 10 。因此，特设置10个队列，并编号为0-9。,计算机怎样实现LSD算法？,分配过程,收集过程,77,55,54，64,21，11,70,02,又称散列过程！,9,小结：排序时经过了反复的“分配”和“收集”过程。当对关键字所有的位进行扫描排序后，整个序列便从无序变为有序了。,70，77,64,54，55,21,11,02,再次分配,再次收集,这种LSD排序方法称为：,基数排序,10,讨论：所用队列是顺序结构，浪费空间，能否改用链式结构？,用链
7、队列来实现基数排序,链式基数排序,实现思路：,针对 d 元组中的每一位分量，把原始链表中的所有记录, 按Kij的取值，让 j = d, d-1, , 1， 先“分配”到radix个链队列中去； 然后再按各链队列的顺序，依次把记录从链队列中“收集”起来； 分别用这种“分配”、“收集”的运算逐趟进行排序； 在最后一趟“分配”、“收集” 完成后，所有记录就按其关键码的值从小到大排好序了。,11,请实现以下关键字序列的链式基数排序： T=（614，738，921，485，637， 101，215，530，790，306）,例:,第一趟分配,e0 e1 e2 e3 e4 e5 e6 e7 e8 e9,6
8、14,738,921,485,637,101,215,530,790,306,f0 f1 f2 f3 f4 f5 f6 f7 f8 f9,原始序列链表：,r0,（从最低位 i = 3开始排序，f 是队首指针，e 为队尾指针）,第一趟收集（让队尾指针ei 链接到下一非空队首指针fi+1 即可）,r0,12,第一趟收集的结果：,e0 e1 e2 e3 e4 e5 e6 e7 e8 e9,614,738,921,485,637,101,215,530,790,306,f0 f1 f2 f3 f4 f5 f6 f7 f8 f9,第二趟分配（按次低位 i = 2 ）,第二趟收集（让队尾指针ei 链接到下
9、一非空队首指针fi+1 ）,r0,r0,13,第二趟收集的结果：,e0 e1 e2 e3 e4 e5 e6 e7 e8 e9,614,738,921,485,637,101,215,530,790,306,f0 f1 f2 f3 f4 f5 f6 f7 f8 f9,第三趟分配（按最高位 i = 1 ）,第三趟收集（让队尾指针ei 链接到下一非空队首指针fi+1 ）,r0,r0,14,1. 排序前后的n个记录都用顺序表r 存储，但建议增开n 个指针分量（转为静态链表形式）；这样在记录重排时不必移动数据，只需修改各记录的链接指针即可。 2.在radix个队列中，每个队列都要设置两 个指针： int
10、 f radix指示队头( f j 初始为空）； int e radix 指向队尾（e j 不必单独初始化)； 分配到同一队列的关键码要用链接指针链接起来。 （注：以上一共增开了n+2 radix个附加指针分量） 3. 待排序记录存入r 中， r0作为头结点；每个记录都包含key分量、othernifo分量和指针域int next分量。 另外，为能单独表示单关键码key的各位，将key改用向量key0d-1来表示之，这样： 第p个记录的关键码的第i位可表示为：rp.keyi; 第p个记录的指针分量可表示为： rp.next,如何编程实现？,先作若干说明：,15,/取第p个关键字的第i 位,/将
11、p指向下一个关键字,队不空，则新元素应链到原队尾元素之后,P是关键字序列r 的指针分量,队首为空吗？空则f(j)新入队元素,队尾新入队的元素地址,一趟“分配”过程的算法流程,16,void RadixSort ( / / 选下一关键字，直到本趟分配完,链表基数排序的算法：,17,j = 0; / 开始从0号队列（总共radix个队）开始收集 while ( f j = 0 ) j+; /若是空队列则跳过 r0.next=p = f j; /建立本趟收集链表的头指针 int last = ej; /建立本趟收集链表的尾指针 for ( k = j+1; k radix; k+) /逐个队列链接（
12、收集） if ( f k ) /若队列非空 rlast.next=f k; last = ek; /队尾指针链接 rlast.next=0; /本趟收集链表之尾部应为0 / RadixSort,注：在此算法中，数组rn被反复使用，用来存放原始序列和每趟收集的结果。记录从未移动，仅指针改变。,18,基数排序算法分析,假设有n 个记录, 每个记录的关键字有d 位，每个关键字的取值有radix个, 则需要radix个队列, 进行d 趟“分配”与“收集”。因此时间复杂度：O ( d ( n+radix ) )。 基数排序需要增加n+2radix个附加链接指针，空间效率低 空间复杂度：O（radix）.
13、 稳定性：稳定。(一直前后有序)。 用途：若基数radix相同，对于记录个数较多而关键码位数较少的情况，使用链式基数排序较好。,特点：不用比较和移动，改用分配和收集，时间效率高！,19,各种内部排序方法的比较 (教材P289）,20,讨论： 若初始记录基本有序，则选用哪些排序方法比较适合？ 若初始记录基本无序，则最好选用哪些排序方法？,答：对基本有序的情况，可选用堆排序、冒泡排序、归并排序等方法； 在基本无序的情况下，最好选用快速排序、希尔排序。,想一想：能选用折半排序么？,21,深深感谢全体同学的支持和配合，使我能顺利完成本课程的教学任务。 你们的聪颖、好学和积极进取精神给我留下了极为深刻的印象，在此衷心祝愿大家： 依靠自身实力取得本课程考试的优异成绩！ 充实而无悔地度过大学时代的每一天！,年轻的朋友们，我们后会有期！,
