基数排序的设计与实现.docVIP

武汉理工大学《数据结构》课程设计说明书  PAGE \* MERGEFORMAT 8  PAGE \* MERGEFORMAT 1 基数排序的设计与实现 摘要: 排序有多种:冒泡,插入,选择,Shell,快速,都是大家所熟悉的,但是大多数学习者可能对基数排序还很陌生.基数排序(Radix Sort):外排序的一种,是对箱排序的改进和推广,它的基本思想是从低位到高位依次对Kj(j=d-1，d-2，…，0)进行箱排序。在d趟箱排序中，所需的箱子数就是基数rd，这就是基数排序名称的由来. 关键词：关键字 基数排序 0、引言 排序（Sorting）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排序成一个按关键字有序的排列。由于待排序的记录数量不同,使得排序过程中涉及的存储器不同,可将排序方法分为两大类:一类是内部排序,指的是待排序记录存放在计算机随机存储器中进行的排序过程；另一类是外部排序,指的是待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程同步中尚需对外存进行访问的排序过程。 内部排序的方法很多，但就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境（如记录的初始排列状态等）下使用。如果按排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序、交换排序、选择排序、归并排序和基数排序五类；如果按内部排序过程中所需的工作量来区分，则可分为3类：（1）简单的排序方法，其时间复杂度为O(n·n)；（2）先进的排序方法，其时间复杂度为O(nlogn)；（3）基数排序，其时间复杂度为O(d·n)。 基数排序（Radix Sorting）是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。它适用于序列长度很大而关键字较小的序列。这个程序主要用于演示基数排序的过程。 1、需求分析 （1）用户根据提示输入10个无序数 （2）回车后输出排好序的10个数 2、基数排序的基本概念 2.1单关键字和多关键字? 文件中任一记录R[i]的关键字均由d个分量 构成。若这d个分量中每个分量都是一个独立的关键字，则文件是多关键字的(如扑克牌有两个关键字：点数和花色)；否则文件是单关键字的， (0≤jd)只不过是关键字中其中的一位(如字符串、十进制整数等)。? 多关键字中的每个关键字的取值范围一般不同。如扑克牌的花色取值只有4种，而点数则有13种。单关键字中的每位一般取值范围相同。 2.1．1实现多关键码排序有两种常用的方法（1） 最高位优先MSD (Most Significant Digit first)（2） 最低位优先LSD (Least Significant Digit first) 2.1.2最高位优先法通常是一个递归的过程：（1） 先根据最高位关键码K1排序,得到若干对象组，对象组中每个对象都有相同关键码K1。 （2） 再分别对每组中对象根据关键码K2进行排序，按K2值的不同，再分成若干个更小的子组，每个子组中的对象具有相同的K1和K2值。（3） 依此重复，直到对关键码Kd完成排序为止。（4） 最后，把所有子组中的对象依次连接起来，就得到一个有序的对象序列。最低位优先法首先依据最低位关键码Kd对所有对象进行一趟排序，再依据次低位关键码Kd-1对上一趟排序的结果再排序，依次重复，直到依据关键码K1最后一趟排序完成，就可以得到一个有序的序列。使用这种排序方法对每一个关键码进行排序时，不需要再分组，而是整个对象组都参加排序。 LSD和MSD??法也可应用于对一个关键码进行的排序。此时可将单关键码 Ki 看作是一个子关键码组： 2.2基数? 设单关键字的每个分量的取值范围均是： C0≤kj≤Crd-1(0≤jd)可能的取值个数rd称为基数。基数的选择和关键字的分解因关键宇的类型而异:(1) 若关键字是十进制整数，则按个、十等位进行分解，基数rd=10，C0=0，C9=9，d为最长整数的位数；(2) 若关键字是小写的英文字符串，则rd=26，Co=a，C25=z，d为字符串的最大长度。 2.3基数排序的基本思想?? 基数排序的基本思想是：从低位到高位依次对Kj(j=d-1，d-2，…，0)进行箱排序。在d趟箱排序中，所需的箱子数就是基数rd，这就是基数排序名称的由来。 3、基数排序数据结构设计 基数排序是典型的LSD排序方法，利用“分配”和“收集”两种运算对单关键码进行排序。在这种方法中，把单关键码 Ki 看成是一个d元组： 其中的每一个分量 ( 1≤ j ≤ d ) 也可看成是一