　　　　　　　　基数排序

　　导入：在常见oi比赛中o(n log n ) 的复杂度的排序（快速排序，归并排序，堆排序)已经够各位看官使用但你是否思考过有没有更优的排序算法呢,想必你一定会说桶排序o(n)的时间复杂度确实让其他算法无法比拟可o（m）

的空间一旦m>10^7该算法就只能尴尬离场了，那么真的没有更优的算法可以胜任这项工作了吗，今天我们介绍一种极优的排序算法——基数排序。

　　关于各种排序的比较可以去膜拜大佬的博客各种排序算法总结

　　基数排序介绍：基数排序是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。
　　 具体做法：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

　　图解: 通过基数排序对数组{53, 3, 542, 748, 14, 214, 154, 63, 616}，它的示意图如下：

#include<iostream>
#define N 10000

using namespace std;

int get(int a[], int n)
{
    int i, max;
    max = a[0];
    for (i = 1; i < n; i++)
        if (a[i] > max)
            max = a[i];
    return max;
} 
void work(int a[], int n, int exp)
{
    int mid[n];
    int i,q[10] = {0};
    for (i = 0; i < n; i++)
        q[ (a[i]/exp)%10 ]++;
    for (i = 1; i < 10; i++)
        q[i] += q[i - 1];

    for (i = n - 1; i >= 0; i--)
    {
        mid[q[ (a[i]/exp)%10 ] - 1] = a[i];
        q[ (a[i]/exp)%10 ]--;
    }
 
    for (i = 0; i < n; i++)
        a[i] = mid[i];
} 
void sort(int a[], int n)
{
    int exp; int max = get(a, n); 
    for (exp = 1; max/exp > 0; exp *= 10)
        work(a, n, exp);
}

int main()
{
    int i;
    int a[N];
    int ilen = (sizeof(a)) / (sizeof(a[0]));
    cout << "before sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;
    sort(a, ilen);   
    cout << "after  sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

好像讲的不是很清楚，我也不太会啦

基数排序

基数排序

推荐阅读

　　　　　　　　基数排序