第9章 内部排序-基数排序10.6 基数排序 (Radix Sort)问题：1. 什么是“多关键字”排序？实现方法？2. 单逻辑关键字怎样“按位值”排序？基本思想： 借助多关键字排序的思想对单逻辑关键字进行排序即：用关键字不同的位值进行排序2多关键字排序例1：对一副扑克牌该如何排序？ 若规定花色和面值的顺序关系为： 花色： 面值：2 3 4 5 6 7 8 9 10 J Q K A 则可以先按花色排序，花色相同者再按面值排序 也可以先按面值排序，面值相同者再按花色排序10.6 基数排序 例2：职工分房该如何排序？ 规定：先以总分排序（职称分工龄分）；总分相同者，再按配偶总分排序，其次按配偶职称、工龄、人口等等排序例3：学生评奖学金如何排序？多关键字排序的实现方法通常有两种： 最高位优先法MSD(Most Significant Digit first) 最低位优先法LSD(Least Significant Digit first)10.6 基数排序 对一副扑克牌的排序若规定花色为第一关键字（高位），面值为第二关键字（低位），则使用MSD和LSD方法都可以达到排序目的MSD方法的思路：先设立4个花色“箱”，将全部牌按花色分别归入4个箱内（每个箱中有13张牌）；然后对每个箱中的牌按面值进行插入排序（或其它稳定算法）。
LSD方法的思路：先按面值分成13堆（每堆4张牌），然后对每堆中的牌按花色进行排序（用插入排序等稳定的算法）用哪种方法更快些？ 单逻辑关键字“按位值”排序设n 个记录的序列为：V0, V1, , Vn-1 ，可以把每个记录Vi 的单关键码 Ki 看成是一个d元组（Ki1, Ki2, , Kid），则其中的每一个分量Kij ( 1 j d ) 也可看成是一个关键字注1： Ki1最高位，Kid最低位；Ki共有d位，可看成d元组；注2： 每个分量Kij (1 j d ) 有radix种取值，则称radix为基数思路：讨论：是借用MSD方式来排序呢，还是借用LSD方式？例：初始关键字序列T=（32,19,27,32*,13，30），请分别用MSD和LSD进行排序，并讨论其优缺点法1（MSD）：原始序列：32,19,27,32*,13，30先按高位Ki1排序：（19,13）,27,（32,32*，30）再按低位Ki2排序：13,19，27,30,32,32*法2（LSD）：原始序列：32,19,27,32*,13，30先按低位Ki2排序：30,32,32*,13,27,19再按高位Ki1排序：13,19,27,30,32,32*MSD存在递归效率受影响LSD只需进行线性扫描用链队列来实现基数排序链式基数排序实现思路： 针对d 元组中的每一位分量，把原始链表中的所有记录, 按Kij的取值,让 j = d, d-1, , 1， 先“分配”到radix个链队列中去； 然后再按各链队列的顺序，依次把记录从链队列中“收集”起来； 分别用这种“分配”、“收集”的运算逐趟进行排序； 在最后一趟“分配”、“收集” 完成后，所有记录就按其关键码的值从小到大排好序了。
实现实现实现实现 以下关以下关键键键键字序列的字序列的链链链链式基数排序式基数排序：T=T=（278278，109109，063063，930930，589589，184184，505505，269269，008008，083083）例例278278063063930930589589109109184184505505269269008008083083第一趟分配第一趟分配e0e1e2e3e4e5e6e7e8e9184083589505063269278930008f0f1f2f3f4f5f6f7f8f9原始序列原始序列链链链链表：表：r0（从最低位（从最低位 i i =3=3开始排序，开始排序，f 是是队队队队首指首指针针针针，e 为队为队为队为队 尾指尾指针针针针）第一趟收集第一趟收集930063083184505278008109589269r0109e0e1e2e3e4e5e6e7e8e9063278269083184505109930589008f0f1f2f3f4f5f6f7f8f9第二趟分配（按次低位第二趟分配（按次低位 i i=2=2）269589063505109184930008278083930063083184505278008109589269第一趟收集的第一趟收集的结结结结果：果：第二趟收集第二趟收集r0r0e0e1e2e3e4e5e6e7e8e9083008930589184109269505063278f0f1f2f3f4f5f6f7f8f9第三趟分配（按最高位第三趟分配（按最高位 i i=1=1）r0排序排序结结结结束束！269930184008083589109063278505269589063505109184930008278083r0第二趟收集的第二趟收集的结结结结果：果：第三趟收集第三趟收集基数排序算法分析假设有n 个记录, 每个记录的关键字有d 位，每个关键字的取值有radix个, 则需要radix个队列, 进行d 趟“分配”与“收集”。
因此时间复杂度：O ( d ( n+radix ) )基数排序需要增加n+2radix个附加链接指针，空间效率低空间复杂度：O（radix）.稳定性：稳定一直前后有序)用途：若基数radix相同，对于记录个数较多而关键码位数较少的情况，使用链式基数排序较好特点：不用比较和移动，改用分配和收集，时间效率高！链表基数排序的算法：void RadixSort (&list, int d, int radix ) int fradix, eradix; for ( int i = 1; i = 0; i- ) /开始做 d 趟分配/收集, i是key的第i位 for ( int j = 0; j radix; j+ ) fj = 0; /初态态各队队列清空 while ( p!= 0 ) / 开始将n个记录记录 分配到radix个队队列 int k = rp. keyi; /取当前记录记录 之key分量的第 i 位 if ( fk = 0) f k =p; /若第k个队队列空, 此记录记录 成为队为队 首；else rek.next=p; /若队队列不空,链链入原队队尾元素之后 ek =p; /修改队队尾指针针，该记录该记录 成为为新的队队尾 p= rp.next; / / 选选下一关键键字，直到本趟分配完 j = 0; / 开始从0号队队列（总总共radix个队队）开始收集 while ( f j = 0 ) j+; /若是空队队列则则跳过过 r0.next=p = f j; /建立本趟收集链链表的头头指针针 int last = ej; /建立本趟收集链链表的尾指针针 for ( k = j+1; k radix; k+) /逐个队队列链链接（收集） if ( f k ) /若队队列非空 rlast.next=f k; last = ek; /队队尾指针链针链 接 rlast.next=0; /本趟收集链链表之尾部应为应为 0 / RadixSort 在此算法中，数组rn被反复使用，用来存放原始序列和每趟收集的结果。
记录从未移动，仅指针改变特点：不用比较和移动，改用分配和收集，时间 效率高！假设有n 个记录, 每个记录的关键字有d 位，每个关键字的取值有radix个, 则需要radix个队列, 进行d 趟“分配”与“收集”因此时间复杂度：O ( d ( n+radix ) )基数排序需要增加n+2radix个附加链接指针，空间效率低空间复杂度：O（radix）.稳定性：稳定一直前后有序)用途：若基数radix相同，对于记录个数较多而关键码位数较少的情况，使用链式基数排序较好1）平方阶(O(n2)排序 一般称为简单排序，例如直接插入、直接选择和冒泡排序；（2）线性对数阶(O(nlgn)排序 如快速、堆和归并排序；（3）O(n1+)阶排序 是介于0和1之间的常数，即01，如希尔排序；按平均时间将排序类 9.7 内部排序方法的比较1、各种方法的时、空优劣判定树模型：如下图所示，说明对a,b,c进行分类的一棵判定树当判断条件成立时，转向左，否则转向右2、比较法分类的下界：O(nlogn)ababcacbcacbcacbcabcbabacbcanoyesyesyesyesyesnononono注意：树高代表比较的代价。
因此只要知道了树高和结点数n的关系，就可以求出用比较法进行排序时的时间代价另外，n个结点的分类序列，其叶子结点共有n!片9.7 内部排序方法的比较17nn20n21nn20n21nlog2nn20n2log2nnn20n1nlog2nnlog2n1nlog2nnlog2nndnn 9.7 内部排序方法的比较18 因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：待排序的记录数目n；记录的大小(规模)；关键字的结构及其初始状态；对稳定性的要求；语言工具的条件；存储结构；时间和辅助空间复杂度等影响排序效果的因素 9.7 内部排序方法的比较 (1)若n较小(如n50)，可采用直接插入或直接选择排序 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。
这两种排序都是不稳定的不同条件下排序方法的选择 外部排序与文件1、外部排序：待排序的记录数量巨大，无法一次调入内存，只能驻留在外存上（磁带、磁盘、CD-ROM）上不能使用内部排序的方法进行排序否则将引起频繁访问外存外部排序主要的时间开销用在信息的内、外存交换上，所以减少I/O时间成为要解决的主要问题1.外部排序的方法外部排序的基本过程由相对独立的两个步骤组成：按可用内存大小,利用内部排序方法，构造若干个记录的有序子序列写入外存，通常称这些记录的有序子序列为 “归并段”;通过“归并”，逐步扩大(记录的)有序子序列的长度，直至外存中整个记录序列按关键字有序为止.例如：假设有一个含10,000个记录的磁盘文件，而当前所用的计算机一次只能对1,000个记录进行内部排序，则首先利用内部排序的方法得到10个初始归并段，然后进行逐趟归并假设进行2路归并(即两两归并)，则第一趟由10个归并段得到5个归并段;第二趟由 5 个归并段得到3个归并段;第三趟由 3 个归并段得到2个归并段;最后一趟归并得到整个记录的有序序列 假设“数据块”的大小为200，即每一次访问外存可以读/写200个记录 则对于10,000个记录，处理一遍需访问外存100次(读和写各50次)。
1)求得10个初始归并段需访问外存100次;2)每进行一趟归并需访问外存100次;3)总计访问外存 100 + 4 100 = 500次若对上述例子采用5路归并,则只需进行2趟归并，总的访问外存的次数为100+2100=300次 一般情况下，假设待排记录序列含 m 个初始归并段，外排时采用 k路归并，则归并趟数s=logkm，显然，随着k的增大或m的减小，归并的趟数将减少，因此对外排而言，通常采用多路归并k 的大小可选，但需综合考虑各种因素2. 多路平衡归并的实现19572959576543276543215595729951649527871225849129385766719224748595输入缓冲区4路平衡归并胜者树及其使用胜者树及其使用977291697516495278712258491。