基数排序

说基数排序之前，我们先说桶排序：

基本思想：是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。
简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。

简略概述：基数排序是通过“分配”和“收集”过程来实现排序。而这个思想该如何理解呢？请看以下例子。

（1）假设有欲排数据序列如下所示：

73 22 93 43 55 14 28 65 39 81

首先根据个位数的数值，在遍历数据时将它们各自分配到编号0至9的桶（个位数值与桶号一一对应）中。

分配结果（逻辑想象）如下图所示：

分配结束后。接下来将所有桶中所盛数据按照桶号由小到大（桶中由顶至底）依次重新收集串起来，得到如下仍然无序的数据序列：

81 22 73 93 43 14 55 65 28 39

接着，再进行一次分配，这次根据十位数值来分配（原理同上），分配结果（逻辑想象）如下图所示：

分配结束后。接下来再将所有桶中所盛的数据（原理同上）依次重新收集串接起来，得到如下的数据序列：

14 22 28 39 43 55 65 73 81 93

观察可以看到，此时原无序数据序列已经排序完毕。如果排序的数据序列有三位数以上的数据，则重复进行以上的动作直至最高位数为止。

分配排序的基本思想：说白了就是进行多次的桶式排序。

基数排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶：O(n)。

实例:

扑克牌中52 张牌，可按花色和面值分成两个字段，其大小关系为：
花色：梅花< 方块< 红心< 黑心
面值：2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

若对扑克牌按花色、面值进行升序排序，得到如下序列：

即两张牌，若花色不同，不论面值怎样，花色低的那张牌小于花色高的，只有在同花色情况下，大小关系才由面值的大小确定。这就是多关键码排序。

为得到排序结果，我们讨论两种排序方法。

方法1：先对花色排序，将其分为4 个组，即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序，最后，将4 个组连接起来即可。

方法2：先按13 个面值给出13 个编号组(2 号，3 号，...，A 号)，将牌按面值依次放入对应的编号组，分成13 堆。再按花色给出4 个编号组(梅花、方块、红心、黑心)，将2号组中牌取出分别放入对应花色组，再将3 号组中牌取出分别放入对应花色组，……，这样，4 个花色组中均按面值有序，然后，将4 个花色组依次连接起来即可。

设n 个元素的待排序列包含d 个关键码{k1，k2，…，kd}，则称序列对关键码{k1，k2，…，kd}有序是指：对于序列中任两个记录r[i]和r[j](1≤i≤j≤n)都满足下列有序关系：

其中k1 称为最主位关键码，kd 称为最次位关键码。

两种多关键码排序方法：

多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序，分两种方法：

最高位优先(Most Significant Digit first)法，简称MSD法：

1）先按k1 排序分组，将序列分成若干子序列，同一组序列的记录中，关键码k1 相等。

2）再对各组按k2 排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd 对各子组排序后。

3）再将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法。

最低位优先(Least Significant Digit first)法，简称LSD法：

1) 先从kd 开始排序，再对kd-1进行排序，依次重复，直到按k1排序分组分成最小的子序列后。

2) 最后将各个子序列连接起来，便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。

【2】代码实现

（1）MSD法实现 【最高位优先(Most Significant Digit first)法】

最高位优先法通常是一个递归的过程：

1. 先根据最高位关键码K1排序，得到若干对象组，对象组中每个对象都有相同关键码K1。
2. 再分别对每组中对象根据关键码K2进行排序，按K2值的不同，再分成若干个更小的子组，每个子组中的对象具有相同的K1和K2值。
3. 依此重复，直到对关键码Kd完成排序为止。
4. 最后，把所有子组中的对象依次连接起来，就得到一个有序的对象序列。

示例代码如下：

#include<iostream>
#include<malloc.h>
using namespace std;

int getdigit(int x,int d)  
{   
    int a[] = {1, 1, 10};     //因为待排数据最大数据也只是两位数，所以在此只需要到十位就满足
    return ((x / a[d]) % 10);    //确定桶号
}  

void  PrintArr(int ar[],int n)
{
    for(int i = 0; i < n; ++i)
        cout<<ar[i]<<" ";
    cout<<endl;
}

void msdradix_sort(int arr[],int begin,int end,int d)  
{     
    const int radix = 10;   
    int count[radix], i, j; 
    //置空
    for(i = 0; i < radix; ++i)   
    {
        count[i] = 0;   
    }
    //分配桶存储空间
    int *bucket = (int *) malloc((end-begin+1) * sizeof(int));    
    //统计各桶需要装的元素的个数  
    for(i = begin;i <= end; ++i)   
    {
        count[getdigit(arr[i], d)]++;   
    }
    //求出桶的边界索引，count[i]值为第i个桶的右边界索引+1
    for(i = 1; i < radix; ++i)   
    {
        count[i] = count[i] + count[i-1];    
    }
    //这里要从右向左扫描，保证排序稳定性 
    for(i = end;i >= begin; --i)          
    {    
        j = getdigit(arr[i], d);      //求出关键码的第d位的数字， 例如：576的第3位是5   
        bucket[count[j]-1] = arr[i];   //放入对应的桶中，count[j]-1是第j个桶的右边界索引   
        --count[j];                    //第j个桶放下一个元素的位置(右边界索引+1)   
    }
    //注意：此时count[i]为第i个桶左边界    
    //从各个桶中收集数据  
    for(i = begin, j = 0;i <= end; ++i, ++j)  
    {
        arr[i] = bucket[j]; 
    }
    //释放存储空间
    free(bucket);   
    //对各桶中数据进行再排序
    for(i = 0;i < radix; i++)  
    {   
        int p1 = begin + count[i];         //第i个桶的左边界   
        int p2 = begin + count[i+1]-1;     //第i个桶的右边界   
        if(p1 < p2 && d > 1)  
        {
            msdradix_sort(arr, p1, p2, d-1);  //对第i个桶递归调用，进行基数排序，数位降 1    
        }
    }  
} 

void  main()
{
    int  ar[] = {12, 14, 54, 5, 6, 3, 9, 8, 47, 89};
    int len = sizeof(ar)/sizeof(int);
    cout<<"排序前数据如下："<<endl;
    PrintArr(ar, len);
    msdradix_sort(ar, 0, len-1, 2);
    cout<<"排序后结果如下："<<endl;
    PrintArr(ar, len);
} 
/*
排序前数据如下：
12 14 54 5 6 3 9 8 47 89
排序后结果如下：
3 5 6 8 9 12 14 47 54 89
 */

（2）LSD法实现 [ 最低位优先(Least Significant Digit first)法 ]

最低位优先法首先依据最低位关键码Kd对所有对象进行一趟排序，

再依据次低位关键码Kd-1对上一趟排序的结果再排序，

依次重复，直到依据关键码K1最后一趟排序完成，就可以得到一个有序的序列。

使用这种排序方法对每一个关键码进行排序时，不需要再分组，而是整个对象组。

以【521 310 72 373 15 546 385 856 187 147】序列为例，具体细节如下图所示：

1.

2.

3.

在数据中最高位为3，进行了三次分配、收集过程后，变成有序数组。

二. 算法分析

平均时间复杂度：O(dn)(d即表示整形的最高位数)

空间复杂度：O(10n) （10表示0~9，用于存储临时的序列）

稳定性：稳定

示例代码如下：

#include<iostream>
#include<malloc.h>
using namespace std;

#define   MAXSIZE   10000

int getdigit(int x,int d)  
{   
    int a[] = {1, 1, 10, 100};   //最大三位数，所以这里只要百位就满足了。
    return (x/a[d]) % 10;  
}  
void  PrintArr(int ar[],int n)
{
    for(int i = 0;i < n; ++i)
    {
        cout<<ar[i]<<" ";
    }
    cout<<endl;
}  
void lsdradix_sort(int arr[],int begin,int end,int d)  
{    
    const int radix = 10;   
    int count[radix], i, j; 

    int *bucket = (int*)malloc((end-begin+1)*sizeof(int));  //所有桶的空间开辟   

    //按照分配标准依次进行排序过程
    for(int k = 1; k <= d; ++k)  
    {  
        //置空
        for(i = 0; i < radix; i++)  
        {
            count[i] = 0;        
        }               
        //统计各个桶中所盛数据个数
        for(i = begin; i <= end; i++) 
        {
           count[getdigit(arr[i], k)]++;
        }
        //count[i]表示第i个桶的右边界索引
        for(i = 1; i < radix; i++) 
        {
            count[i] = count[i] + count[i-1];
        }
        //把数据依次装入桶(注意装入时候的分配技巧)
        for(i = end;i >= begin; --i)        //这里要从右向左扫描，保证排序稳定性   
        {    
            j = getdigit(arr[i], k);        //求出关键码的第k位的数字， 例如：576的第3位是5   
            bucket[count[j]-1] = arr[i];    //放入对应的桶中，count[j]-1是第j个桶的右边界索引 
            --count[j];                     //对应桶的装入数据索引减一  
        } 

        //注意：此时count[i]为第i个桶左边界  

        //从各个桶中收集数据
        for(i = begin,j = 0; i <= end; ++i, ++j)  
        {
            arr[i] = bucket[j];    
        }        
    }     
    free(bucket);   
}  

void  main()
{
    int  br[10] = {20, 80, 90, 589, 998, 965, 852, 123, 456, 789};
    cout<<"原数据如下："<<endl;
    PrintArr(br,10);
    lsdradix_sort(br, 0, 9, 3);
    cout<<"排序后数据如下："<<endl;
    PrintArr(br, 10);
}
/*
原数据如下：
20 80 90 589 998 965 852 123 456 789
排序后数据如下：
20 80 90 123 456 589 789 852 965 998
*/