详细解释参考:
http://en.wikipedia.org/wiki/Radix_sort
1,"基数排序法"(radix sort)则是属于"分配式排序"(distribution sort),基数排序法又称"桶子法"(bucket sort)或bin sort.
它是透过键值的部份资讯,将要排序的元素分配至某些"桶"中,藉以达到排序的作用.
复杂度分析:
基数排序法是属于稳定性的排序,其时间复杂度为O(kN),其中k为key的长度,而N为个数.
空间复杂度为O(kN)。
2,基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。
LSD的基数排序适用于位数小的数列,如果位数多的话,使用MSD的效率会比较好
3,以LSD为例,假设原来有一串数值如下所示:
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值,在走访数值时将它们分配至编号0到9的桶子中:
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
接下来将这些桶子中的数值重新串接起来,成为以下的数列:
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配,这次是根据十位数来分配:
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
接下来将这些桶子中的数值重新串接起来,成为以下的数列:
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
4,实例代码:
#include <iostream>
using namespace std;
int maxbit(int data[],int n) //辅助函数,求数据的最大位数
{
int d = 0;
int * tmp = new int[n];
for(int i = 0 ;i < n;i++)
tmp[i]= data[i];
for(int i = 0;i < n;i++)
{
int p =1;
while(tmp[i]/10 > 0)
{
p++;
tmp[i] = tmp[i]/10;
}
if(d < p) d = p;
}
delete [] tmp;
return d;
}
void radixsort(int data[],int n) //基数排序
{
int d = maxbit(data,n); //最大位数
int * tmp = new int[n];
int * count = new int[10]; //计数器
int radix = 1;
for(int i = 0; i< d;i++) //进行d次排序
{
int k;
for(int j = 0;j < 10;j++)
count[j] = 0; //每次分配前清空计数器
for(int j = 0;j < n; j++)
{
k = (data[j]/radix)%10; //统计每个桶中的记录数
count[k]++; //懂
}
for(int j = 1;j < 10;j++)
count[j] = count[j-1] + count[j]; //将tmp中的位置依次分配给每个桶
//这里根据基数把元素放到tmp中. 从后往前放,保证上一次的次序
for(int j = n-1;j >= 0;j--) //将所有桶中记录依次收集到tmp中
{
k = (data[j]/radix)%10;
count[k]--;
tmp[count[k]] = data[j];
}
for(int j = 0;j < n;j++) //将临时数组的内容复制到data中
data[j] = tmp[j];
//显示每步排序完毕后的结果
for(int j=0;j<n;j++)
cout<<data[j]<<" ";
cout<<endl;
radix *= 10;
}
delete [] tmp;
delete [] count;
}
void Output(int data[], int n)
{
for(int i = 0 ; i < n ; i++ )
cout << data[i] << " ";
cout << endl;
}
int main()
{
int data[]={73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
int n=sizeof(data)/sizeof(data[0]);
radixsort(data,n);
Output(data,n);
return 0;
}
分享到:
相关推荐
包括了基数排序的实现代码和流程图。 先对个位数字进行统计,然后根据个位进行排序,然后对十位进行统计,然后根据十位进行排序,即可获得最终结果。 时间效率:待排序列为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 冒泡 快排 选择排序 基数排序 希尔排序 折半插入排序 等