§10.6.2基数排序 §10.6.2基数排序 (36,5.10,16,98.95,47,32,3648) 一般情况 第1鹅箱排序 2箱排序 设年记要R即的k@y均由阶分是KKK-构成 分 多关字文件：d个分量为立的k时 0110 0105 单关键字文件：每个分量是k©y中的1位，只讨论这种情况。 1 10,16 设每位取值范相同： 232 32,36,36 Co≤K≤Cd1(0≤<d 4 47,48 这里， rd称为煎， d为key的位数， 55,95 若k©y为十进制整数，按位分解后rd=10,C。=0,Cg=9 636,16,36 8 747 ■排序算法 898,48 8 丛低位到高位依次对心(j=d-1,d-2,,0)进行d慧箱排序，所需的箱 9 95,98 学为 收集 #defin KeySize4l设a=4 10,32,5,95,36,16,36,47,98,48 05,10,16,32,36,364748,95,98 #define Radix10rd为10 箱子用队列示，其中的点 各煎样序前要求演空箱子，分配和收燕须按FFO进行，箱于用随拟列囊示， 竹外 定的接序，否则结果可能有。 不再在敏量级上大于0(，上述排序时间是⊙问 §10.6.2基数排序 S10.62基数排序 void Distribute(SeqList R,LinkQueue B[],intj{ void RadixSort(SegList R){ iti,k,t:楼关输字分量分配，进入此过理时各箱子为空 ∥对R0.n-1]徽基数排序，设keys为非负整数 j户KeySize-j:墙j换第为从个位起算，个位是第1位 I且位数不超过KeySize for(i=0:iknm;it+)(归描R,装箱 LinkQueue B[Radix];M0个箱子 k=R可.key: int i; for与1；t对；t-)k=k10;∥法掉koy的后j1位 k=k%10;取Key的第位数字张 for(i0;i<Radix;++)物始化 EnQueue(&Bk灯，R可方将R可装入籍于Bk灯 InitQueue(&B门：清空箱子 for(i=KeySize-1;i>=0;i-){ 对位箱排序，从低位到高位进行d髓箱排序 void Collect(SeqList R,LinkQueue B[]){ Distribute(R,B,i方分 it=0,上体次连接各非空箱子，完成后使各箱子变空 Collect(R,B方收第 for(=O:j<Radix;jt+)I精辅子的内客依FIFO序收集到R中 while(IQueu©Empty(&BjD)考是链飘列，只需黄厘藏旋 R[i++]=DeQueue(&B[j]); 510.62基数排序 $10.7各种排序方法的比较和选择 ■链式基数排序：文件不是以向量形式，而是以单链表形式给出。 “选择因囊：实例规模，记录大小，k©y的结构及初蛤状态，对穗定性的 。时间：线性阶 要求，存储结构，时闻和辅助空向的要求，语言工具（指针）。 箱子初始化：Ord 比较 分配时间：O(),不计求第位数字的时间 n 直接洲入直接选操■泡排序维排序 快速排序 收集收集：O(n+rd,链式为Ord d越总时间：O(d(2n+rd),链式为O(d(ntrd】 4000 5.67 17.30 15.78 0.13 0.07 T(n)=O(n)if d=0(1)and rd=0(1)~O(n) 8000 23.15 29.43 64.03 0.28 0.17 ◆设ky是十进制草数，d是常败吗？ 10000 35.43 46.02 99.10 0.35 0.22 若n个keys的取值范国是0~nk,(常数k>1),则key的位数是： 15000 80.23 103.00 223.28 0.58 0.33 d=logon=klog on=(klgn) 机20000 143.67 185.05 399.47 0.77 0.47 因此，基数排序的时间是Olgn)。但是可将其改为n进制表示： 抛20000 0.05 8578 0.03 0.75 623 rd=n,d=lognk=k,T(n)=O(k(n+n))=O(n) 轴助空间：O(n+rd 减20000286.92 199.00 584.67 0.80 0.2 对key的要求： 说明 穗定排序：要求第1整跑定，其余各施必须穗定。 直接选择无论k和是香相等，均交换：快排用中间元触划分元。 33 13 §10.6.2 基数排序 第1趟箱排序 分配： 0 10 1 2 32 3 4 5 5,95 6 36,16,36 7 47 8 98,48 9 收集： 10,32,5,95,36,16,36,47,98,48 （36,5,10,16,98,95,47,32,36,48） 第2趟箱排序 分配： 0 05 1 10,16 2 3 32,36,36 4 47,48 5 6 7 8 9 95,98 收集： 05,10,16,32,36,36,47,48,95,98 „ 各趟排序前要求清空箱子，分配和收集须按FIFO进行，箱子用链队列表示。 „ 除第1趟外，其余各趟一定要是稳定的排序，否则结果可能有错。 „ m不再在数量级上大于O(n)，故上述排序时间是O(n) 14 §10.6.2 基数排序 „ 一般情况 设任一记录R[i]的key均由d个分量 构成 ™多关键字文件：d个分量皆为独立的key ™单关键字文件：每个分量是key中的1位，只讨论这种情况。 设每位取值范围相同： C0≤Kj ≤Crd-1 (0≤j﹤d) 这里，rd称为基数，d为key的位数。 若key为十进制整数，按位分解后rd＝10，C0＝0，C9＝9 „ 排序算法 从低位到高位依次对Kj （j＝d-1,d-2,…,0）进行d趟箱排序，所需的箱 子数为基rd。 #defin KeySize 4 //设d＝4 #define Radix 10 //基rd为10 typedef RecType DataType; //各箱子用链队列表示，其中的结点数 据类型改为与本章的记录类型一致 d 1 i 1 i 0 i K K ...K − 15 §10.6.2 基数排序 void RadixSort( SeqList R ){ //对R[0..n-1]做基数排序，设keys为非负整数， //且位数不超过KeySize LinkQueue B[Radix]; //10个箱子 int i； for ( i=0; i<Radix; i++ ) //初始化 InitQueue(&B[i]); //清空箱子 for( i=KeySize-1; i>=0; i-- ) { //对位i箱排序，从低位到高位进行d趟箱排序 Distribute( R,B,i ); //分配 Collect( R,B ); //收集 } } 16 §10.6.2 基数排序 void Distribute( SeqList R, LinkQueue B[ ], int j ){ int i，k，t； //按关键字j th分量分配，进入此过程时各箱子为空 j=KeySize - j; //将 j 换算为从个位起算，个位是第1位 for ( i=0; i<n; i++ ) { //扫描R，装箱 k=R[i].key; for( t=1; t<j; t-- ) k=k/10; //去掉key的后j-1位 k=k%10; //取key的第j位数字k EnQueue( &B[k],R[i] ); //将R[i]装入箱子B[k] } } void Collect( SeqList R, LinkQueue B[ ] ){ int i=0, j; //依次连接各非空箱子，完成后使各箱子变空 for ( j=0; j<Radix; j++ ) //将j th箱子的内容依FIFO序收集到R中 while ( !QueueEmpty (&B[ j ]) ) //若是链队列，只需首尾链接 R[i++]=DeQueue( &B[ j ]); } 17 §10.6.2 基数排序 „ 链式基数排序：文件R不是以向量形式，而是以单链表形式给出。 „ 时间：线性阶 箱子初始化：O(rd) 分配时间：O(n)，不计求第j位数字的时间 收集收集：O(n+rd)，链式为O(rd) d趟总时间：O( d(2n+rd) )，链式为O( d(n+rd) ) T(n)=O(n) if d=O(1) and rd=O(1) ～ O(n) ™设key是十进制整数，d是常数吗？ 若n个keys的取值范围是0 ～nk，(常数k>1)，则key的位数是： d＝log10nk＝klog10n＝O(klgn) 因此，基数排序的时间是O(nlgn)。但是可将其改为n进制表示： rd＝n， d＝lognnk＝k，T(n)＝O( k(n+n) )=O(n) „ 辅助空间：O(n+rd) „ 对key的要求： „ 稳定排序：要求第1趟稳定，其余各趟必须稳定。 18 §10.7 各种排序方法的比较和选择 „ 选择因素：实例规模，记录大小，key的结构及初始状态，对稳定性的 要求，存储结构，时间和辅助空间的要求，语言工具（指针）。 „ 比较 0.07 0.17 0.22 0.33 0.47 0.23 0.28 0.13 0.28 0.35 0.58 0.77 0.75 0.80 15.78 64.03 99.10 223.28 399.47 0.03 584.67 17.30 29.43 46.02 103.00 185.05 185.78 199.00 5.67 23.15 35.43 80.23 143.67 0.05 286.92 随 4000 8000 10000 15000 机 20000 增 20000 减 20000 n 直接插入 直接选择 冒泡排序 堆排序 快速排序 „ 说明 直接选择无论k和i是否相等，均交换；快排用中间元做划分元