基数排序是非比较排序算法,算法的时间复杂度是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，如需转载请自行联系原作者
