基数排序是非比较排序算法,算法的时间复杂度是O(n). 相比于快速排序的O(nlgn),从表面上看具有不小的优势.但事实上可能有些出入,因为基数排序的n可能具有比较大的系数K.因此在具体的应用中,应首先对这个排序函数的效率进行评估。
基数排序不仅仅只用在数字的排序上,由于关键字的不同,可以选择不同的排序方式。要想采用基数排序,我们需要至少两种关键字,而且要依照关键字的优先级从低到高的顺序进行操作。
在数字问题上,要得到一个数列排序: 42 58 5 32,这样的数字,我们可以通过个位与十位来进行排序,分为两个桶子,分别为0~9的个位和0~9的十位。 具体的排序过程(红色字体表示正在排序的数位)如下:
第一次排序(个位):
桶的编号:0 1 2 3 4 5 6 7 8 9
个数: 0 0 2 0 0 1 0 0 1 0
收集桶:42 32 5 58
第二次排序(十位):
桶的编号:0 1 2 3 4 5 6 7 8 9
个数: 1 0 0 1 1 0 0 0 0 0
收集桶:5 32 42 58
还可以用在其他问题上,例如,我们要把52张四种花色的扑克牌进行依次从小到大的排序,其中黑桃<红桃<方片<梅花。
这个问题的话,关键字为0~K和花色,而且花色的优先级大于数字,所以我们要先选择数字0~K先做一次排序,也就是分13个桶,分为标记为0~K,这样每个桶内就存在不同的四张花色的牌,这样我们收集起来了,然后我们再分4个桶,标记为不同的花色,然后把13个标记为数字的桶中的扑克牌依次放进这些桶内,最终我们可以不通过比较数字的大小和花色,就可以得到排序的结果了。
//数组实现 #include<iostream> using namespace std; int data[10]={73, 22, 93, 43, 55, 14, 50, 65, 39, 81}; int tmp[10]; int count[10]; int maxbit(int data[],int n)//取数据位数 { int d=1; for(int i=0;i<n;i++) { int c=1; int p=data[i]; while(p/10) { p=p/10; c++; } if(c>d) d=c; } return d; } void RadixSort(int data[],int n) { int d=maxbit(data,n);//获取数据最大位数 int r=1; for(int i=0;i<d;i++) { for(int i=0;i<10;i++)//装桶之前要先清桶--10个桶(0~9) count[i]=0; for(int i=0;i<n;i++) //记录每个桶的记录数 { int k=data[i]/r; int q=k%10; count[q]++;//记录 } for(int i=1;i<10;i++)//计算位置 { count[i]+=count[i-1]; //cout<<count[i]<<" "; } for(int j=n-1;j>=0;j--) { int p=data[j]/r; int s=p%10; tmp[count[s]-1]=data[j];//由于如果此位相同的数字有两个 那计数是从0开始的,所以它的位置就应该-1 count[s]--; //cout<<data[j]<<" "; } for(int i=0;i<n;i++) { data[i]=tmp[i]; //cout<<tmp[i]<<" "; } // cout<<endl; r=r*10;//不断循环 } } int main() { cout<<"基数排序c++实现"<<endl; //cout<<maxbit(data,10)<<endl; cout<<"排序之前的数值:"; for(int i=0;i<10;i++) cout<<data[i]<<" "; cout<<endl; RadixSort(data,10); cout<<"排序之前的数值:"; for(int i=0;i<10;i++) cout<<data[i]<<" "; cout<<endl; return 0; }
本文转自cococo点点博客园博客,原文链接:http://www.cnblogs.com/coder2012/archive/2012/10/13/2722907.html,如需转载请自行联系原作者