基数排序
使用例子来讲基数排序是最直观的。假设有10个0~999之间的十进值数,分别是64 8 216 512 27 729 0 1 343 125,对这几个数如何使用基数排序呢?基数排序顾名思义跟基数有关系,这里的数都是十进制的,所以基数Radix = 10。十进制数在某一位上最多有10个不同可能,比如说个位上的数,只能是0~9之间的某一个。假如这些数先按个位上的数的大小排序,那就可以设置10个桶,分别用来装这些可能数。但是每个桶只能装一个数,如果有两个数个位上的数是相同的怎么办?我们可以把这两个数放到表里面,桶保存的是这个表,而不再是某个数了。这样把这10个数都装完之后,按顺序打印桶里的数,就得到了按个位排序的顺序。同理,我们再用十位,百位来排序,最后一趟排序就能得到正确的结果。在这个排序过程中,按地位排序能得到正确的结果,但是如果按高位排序则不能。
描述一下按基数排序的步骤:
(1)首先设置基数大小的桶,桶里的每个元素都是用来保存表的;
(2)先按个位排序,遍历待排序序列,如果它个位上的数是0,则装进第0个桶里的链表里,如果是1,则装进第1个桶里的链表....
(3)按顺序收集各个桶里的数,这样得到的新序列就是按个位排序的结果
(4)在按个位排序的结果上,再分别用十位上的数排序,过程同上
(5)收集按十位排序的结果
(6)接着按百位、千位,直到最高位排序,最后一趟收集的结果就是排序的正确序列。
我们用图来形象的展示基数排序过程,首先是设置10个桶,初始时h[i]和t[i]都指向这些桶,其中,h[i]始终指向着这个桶,t[i]则指向该桶链表的最后一个元素,方便插入元素,为了方便,我使用了头结点,h[i]就是头结点。待排序序列表L,一次排序完成后,L收集各个桶里表,收集顺序是:
(1)L指向第一个非空桶的链表的第一个元素,该链表的表尾是t[i]
(2)t[i]->next是下一个非空桶的链表的第一个元素,然后依次将非空的桶按首尾顺序连接起来。
然后按十位排序,其过程如下图
接着按百位排序,过程省略。给出示意性代码,分别给出了链表L和桶都使用头结点和都不使用头结点的代码,使用头结点要注意头结点的复用问题,不使用同节点在要考虑第一个元素的特殊情况。首先是声明:
#define Radix 10 //基数
/********对链表的定义*********/
typedef int ElementType;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
struct Node {
ElementType element;
Position next;
};
/********定义结束************/
Position h[Radix];//保存每个表的头元素
Position t[Radix];//保存每个表的尾元素
/*获取某个数(n)的某个位(place)上的值*/
int getPlace(int n,int place) {
int div = 1;
int i = 0;
for(i = 1; i < place; i++)
div *= Radix;
return (n / div) % Radix;
}
链表L和桶都使用头结点的情况:
/*初始化保存表头的数组*/
void initH() {
int i = 0;
for(; i <Radix; i++) {
h[i] = malloc(sizeof(struct Node));
h[i]->next = NULL;
}
}
/*是一趟基数排序,place是位,L存放待排序数据*/
List sort(int place,List L) {
int i = 0;
//每次排序前都要清除桶与前一次排序的联系
for(i = 0; i < Radix; i++) {
t[i] = h[i];
t[i]->next = NULL;
}
//为了复用头结点,需要先保存起来,也就是说在整个基数排序过程中,它始终是链表的头结点
Position head = L;
Position p = NULL;
L = L->next;//第一个元素
while(L != NULL) {
p = L;
L = L->next;
int index = getPlace(p->element,place);
p->next = NULL;
t[index]->next = p;
t[index] = p;
}
//复用头结点
L = head;
L->next = NULL;
Position q = L;
//进行合并
for(i = 0; i < Radix; i++) {
if(h[i]->next != NULL) {
q->next = h[i]->next;
q = t[i];
}
}
return L;
}
不使用头结点的代码:
/*初始化桶*/
void InitHT() {
int i = 0;
for(i = 0; i < Radix; i++) {
h[i] = t[i] = NULL;
}
}
List sortNoHead(int place,List L) {
//每次排序前都需要初始化桶,这个很关键,要清除它与上次的关系
InitHT();
Position p = NULL;
while(L != NULL) {
//当前正在处理的节点
p = L;
//位置很重要,如果放到最后的话,L当前指向的节点已经改变了
L = L->next;
//这句话很重要,切断它与原来链表的联系
p->next = NULL;
//当前位上的数
int index = getPlace(p->element,place);
//如果是该表的第一个数,就将h[index]和t[index]指向它,否则,将它加入链表后面
if(t[index] == NULL) {
h[index] = t[index] = p;
}else {
t[index]->next = p;
t[index] = p;
}
}
//合并
Position tmp = NULL;
int i = 0;
for(i = 0; i < Radix; i++) {
if(h[i] != NULL) {
//不适用头结点,则要考虑tmp和L第一次指向非空表时的特殊情况
if(tmp == NULL) {
tmp = h[i];
L = h[i];
}
else {
tmp->next = h[i];
tmp = t[i];
}
}
}
return L;
}
以上代码是用C语言写的,C的参数传递方式是值传递,我们看到如果把链表L传到函数里面,在函数里面使用的是L的副本L',L'指向的内存发生了变化,所以我们必须要返回L'。
时间复杂度分析
一趟基数排序的过程:把N个元素分别放到不同的桶里需要O(N),之后需要收集各个桶,重新组成链表,总共有Radix个桶,需要时间O(Radix)。所以一趟排序的时间是:O(N + Radix)。如果待排序序列的最高有P位,也就是需要P趟排序,所以总时间是:
O(P(N + Radix)),N待排序元素个数,Radix桶数,P排序的趟数。
快速排序的时间复杂度是O(NlogN),看上去基数排序的趟数要少一下,但是快速排序每一趟执行的时间要长得多,快速排序通常可以比基数排序更好的利用硬件缓存,logN的因子不都那么大)。如果待排序序列中有很大的数,其余的则很小,这样就不太好了,而且基数排序还有保存链表的附加开销。有一点需要注意:基数排序必须是稳定的。
分享到:
相关推荐
包括了基数排序的实现代码和流程图。 先对个位数字进行统计,然后根据个位进行排序,然后对十位进行统计,然后根据十位进行排序,即可获得最终结果。 时间效率:待排序列为n个记录,10个关键码,关键码的取值范围为0...
基数排序基数排序基数排序基数排序基数排序
数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序
数据结构之基数排序数据结构之基数排序数据结构之基数排序数据结构之基数排序数据结构之基数排序
基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字拆分成数字位。并且按照数字位的值对数据项进行排序,这种方法不需要进行比较操作。 为了尽可能少的...
基数排序法用链表完成使用C语言适用于刚入门的学者
基数排序过程及程序基数排序过程及程序基数排序过程及程序基数排序过程及程序
这边所要介绍的「基数排序法」(radix sort)则是属于「分配式排序」(distribution sort),基数排序法又称「桶子法」(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些「桶...
基数排序C语言实现
1.需求分析 ①.问题描述 给出一组数据,按照最低位优先的方法完成基数排序。多关键码排序按照从最主位关键码到最次位或从最次位到最主位关键码的顺序逐次排序。
基数排序算法 java实现 还有基数排序的原理文档
插入排序 冒泡排序 堆排序 基数排序 选择排序 快速排序的源码 java实现
排序算法很多,下面有基数排序,堆排序,希尔排序,直接插入排序的代码和思路
算法导论之基数排序,桶排序。基数排序是利用在各个位上进行计数排序,是一种线性排序
8646 基数排序 时间限制:1000MS 内存限制:1000K 提交次数:0 通过次数:0 题型: 编程题 语言: 无限制 描述 用函数实现基数排序,并输出每次分配收集后排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二...
Radix Sort (基数排序)排序算法
基数排序算法,这是分不错的算法,实现起来有点难,用静态链表实现,每次改变结点的指向,希望有用,多多指教
网上的一些基数排序都是用链表的,写了个非链表的例子
排序算法中的基数排序,更重要的是会算时间复杂度,基数排序可以说是以计数排序位基础的,只不过变成了一位一位来或者一个字节一个字节来,每位或者每个字节都过了一遍,则排序完毕。很简单的程序,在code::block IDE...
常用排序效率PK 冒泡 快排 选择排序 基数排序 希尔排序 折半插入排序 等