基数排序的设计与实现

1、 基数排序的设计与实现摘要:排序有多种：冒泡,插入，选择,Shell,快速，都是大家所熟悉的,但是大多数学习者可能对基数排序还很陌生.基数排序(RadixSort):外排序的一种,是对箱排序的改进和推广，它的基本思想是从低位到高位依次对Kj(j=d-1,d-2,，0)进行箱排序。在d趟箱排序中，所需的箱子数就是基数rd,这就是基数排序名称的由来.关键词：关键字基数排序0、引言排序(Sorting)是计算机程序设计中的一种重要操作，它的功能是将一个数据元素(或记录)的任意序列，重新排序成一个按关键字有序的排列。由于待排序的记录数量不同,使得排序过程中涉及的存储器不同,可将排序方法分为两大类:一类

2、是内部排序,指的是待排序记录存放在计算机随机存储器中进行的排序过程；另一类是外部排序,指的是待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程同步中尚需对外存进行访问的排序过程。内部排序的方法很多，但就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境(如记录的初始排列状态等)下使用。如果按排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序、交换排序、选择排序、归并排序和基数排序五类；如果按内部排序过程中所需的工作量来区分，则可分为3类：(1)简单的排序方法，其时间复杂度为O(nn)；(2)先进的排序方法，其时间复杂度为O

3、(nlogn)；(3)基数排序，其时间复杂度为O(dn)。基数排序(RadixSorting)是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。它适用于序列长度很大而关键字较小的序列。这个程序主要用于演示基数排序的过程。1、需求分析（1）用户根据提示输入10个无序数（2）回车后输出排好序的10个数2、基数排序的基本概念单关键字和多关键字.0.1H.d-1文件中任一记录Ri的关键字均由d个分量气叫叫构成。若这d个分量中每个分量都是一个独立的关键字，则文件是多关键字的（如扑克牌有两个关键字：点数和花色）；否则文件是单关键字的，好（0Wjd）只不过是关键字中其中的一位（如字符串、十进制整数等

4、）。多关键字中的每个关键字的取值范围一般不同。如扑克牌的花色取值只有4种，而点数则有13种。单关键字中的每位一般取值范围相同。2.11实现多关键码排序有两种常用的方法（1）最高位优先MSD（MostSignificantDigitfirst）（2）最低位优先LSD（LeastSignificantDigitfirst）2.1.2最高位优先法通常是一个递归的过程：（1）先根据最高位关键码K1排序，得到若干对象组，对象组中每个对象都有相同关键码K1。（2）再分别对每组中对象根据关键码K2进行排序，按K2值的不同，再分成若干个更小的子组，每个子组中的对象具有相同的K1和K2值。（3）依此重复，直到对

5、关键码Kd完成排序为止。（4）最后，把所有子组中的对象依次连接起来，就得到一个有序的对象序列。最低位优先法首先依据最低位关键码Kd对所有对象进行一趟排序，再依据次低位关键码Kd-1对上一趟排序的结果再排序，依次重复，直到依据关键码K1最后一趟排序完成，就可以得到一个有序的序列。使用这种排序方法对每一个关键码进行排序时，不需要再分组，而是整个对象组都参加排序。LSD和MSD方法也可应用于对一个关键码进行的排序。此时可将单关键码Ki看作是一个子关键码组：(K；,K；,町)基数设单关键字的每个分量的取值范围均是：CWkWC(OWjd)可能的取值个数0jrd-1rd称为基数。基数的选择和关键字的分解因

6、关键宇的类型而异：若关键字是十进制整数，则按个、十等位进行分解，基数rd=10,C=0,C=9,09d为最长整数的位数；(2)若关键字是小写的英文字符串，则rd=26,C=a,C=z,d为字符串的o25最大长度。基数排序的基本思想基数排序的基本思想是：从低位到高位依次对Kj(j=d-1,d-2,，0)进行箱排序。在d趟箱排序中，所需的箱子数就是基数rd,这就是基数排序名称的由来。3、基数排序数据结构设计基数排序是典型的LSD排序方法，利用“分配”和“收集”两种运算对单关键码进行排序。在这种方法中，把单关键码Ki看成是一个d元组：(町，K沁,町)其中的每一个分量(1WjWd)也可看成是一个关键码

7、。分量，(1WjWd)有radix种取值，则称radix为基数。例如，关键码984可以看成是一个3元组(9,8,4),每一位有0,1,，9等10种取值，基数radix=10。关键码data可以看成是一个4元组(d,a,t,a),每一位有a,b,，z等26种取值，radix=26。针对d元组中的每一位分量，把对象序列中的所有对象，按丘；的取值，先“分配”到rd个队列中去。然后再按各队列的顺序，依次把对象从队列中“收集”起来，这样所有对象按取值人，排序完成。如果对于所有对象的关键码KO,K1,，Kn-1,依次对各位的分量，让j=d,d-1,1,分别用这种“分配”、“收集”的运算逐趟进行排序，在最后

8、一趟“分配”、“收集”完成后，所有对象就按其关键码的值从小到大排好序了。各队列采用链式队列结构，分配到同一队列的关键码用链接指针链接起来。每一队列设置两个队列指针：intfrontradix指示队头，intrearradix指向队尾。为了有效地存储和重排n个待排序对象，以静态链表作为它们的存储结构。在对象重排时不必移动对象，只需修改各对象的链接指针即可。基数排序的“分配”与“收集”过程第一趟第诞分配（按最職reHre1re2.黑灯w4re|Vwh比工rearelJ第1趟收集基数排序的“分配”与“收集”过程第二趟nf.rc2re3：r?l：r打怖同冷|：z區聞9第2趙收集基数排序的“分配”与“收

9、集”过程第三趟：hi川-|rIiI屈而IITiT-Tin黑趟分配（按側珈i=1）re0r?Ulre?reSre451re6：储R挖圧re1）第谨臊算法基数排序依次对键值的个为位到高位逐位循环按键值的当前位将链表拆分为10个队列链表按对应09的顺序将10个链表收集成一个链表4、基数排序的算法分析基数排是稳定的排序方法,排序文件可以r数组形式给出，也可以是以单链表形式给出（此时为链式的基数排序）则可通过修改出队和人队函数使表示箱子的链队列无须分配结点空间，而使用原链表的结点空间。人队出队操作亦无需移动记录而仅需修改指针。虽然这样一来节省了一定的时间和空间，但算法要复杂得多，且时空复杂度就其数量级而

10、言并未得到改观。下面是从时间和空间复杂度上极其稳定性的一些基本分析:若每个关键码有d位，需要重复执行d趟“分配”与“收集”。每趟对n个对象进行“分配”，对radix个队列进行“收集”。总时间复杂度为O(d(n+radix)若基数radix相同，对于对象个数较多而关键码位数较少的情况，使用链式基数排序较好。基数排序是稳定的.基数排序所需的辅助存储空间为O(n+rd)。5基数排序需要增加n+2radix个附加链接指针5、编程实现及测试结果5.1C语言实现的基数排序的代码:#include#include#include#include#defineKEYN4structeleintkey;stru

11、ctele*link;voidbases(ele*h)ele*head10,*tail10,*p,*u;intfactor=1,i,j;p=*h;for(i=0;iKEYN;i+)for(j=0;jlink;j=(p-key/factor)%10;if(headj=NULL)headj=p;elsetailj-link=p;tailj=p;tailj-link=NULL;p=u;p=NULL;for(j=0;jlink=headj;u=tailj;factor*=10;*h=p;voidmain()ele*h,*u;inta10;coutvv输入10个数：vvendl;for(inti=0;i

12、ai;h=NULL;/*先形成一个空链表*/for(i=0;iv10;i+)/*任意形成一个链表*/u=new(ele);u-key=ai;u-link=h;h=u;coutvv排序后的10个数：vvendl;bases(&h);/*排序*/for(u=h;u;u=u-link)/*顺序输出链表各表元的链值*/coutkey;coutendl;getch();5.2程序运行结果：6、不足之处该程序虽然实现了基数排序但没有达到与其他排序进行比较的功能，且只能实现十个数的排序，还有很多地方需要改进。7、设计体会为期一周的课程设计紧张而充实，时间虽然不长，但还是让我学到了不少新的东西，单就我个人课程设计而言，我对基数排序的基本概念及其排序过程有了一定的了解。当然通过本次课程设计，我也发现了自己的不足之处，在知道基数排许的概念和排序过程之后，便开始了基数排序的算法分析和设计，但在数据存储结构的选择上卡住了，不知道是选择队列还是数组或者链