基数排序

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

上一篇:通用Digital CTO:工业人工智能所面临的4点特殊挑战


下一篇:ASP.NET MVC5+EF6+EasyUI 后台管理系统(82)-Easyui Datagrid批量操作(编辑,删除,添加)