基数排序

"次位优先"LSD (Least sgnificant digital)基数排序动图演示

 

 

 

#include <iostream>
#include <queue>
#include <list>

using namespace std;

// 求出数组a中最大的位数，即求出最大的数字的位数
int getDigit(int a[], int n)
{
    // 先找出数组中最大的那个数 
    int Max = -1;
    for(int i = 0; i < n; ++i) 
    {
        if(a[i] > Max)
            Max = a[i];
    }
    int k = 1;
    // 再求这个最大的数有几位 
    while(Max/10 > 0)
    {
        k++;    // k表示最大的数字的位数 
        Max /= 10; 
    }
    
    return k;
}

// 正整数的基数排序 
// n表示待排数组a中元素的个数
void radixSort(int a[], int n)
{    
    
    int k = getDigit(a, n); 
    // 这里list也可以用queue代替 
    list<int> L[10];
    int r = 10;
    while(k--)
    {
        for(int i = 0; i < n; ++i)
        {
            // 把数放入对应的链表下面 
            // 比如取出个位数，即有a[i]%10/1，取出十位数，即有a[i]%100/10
            // 因此可以得到下面的公式 
            int p = (a[i]%r) / (r/10);
            L[p].push_back(a[i]);
        }
        
        
        int j = 0;
        // 把链表上的数字重新分配回原数组a，同时链表也被清空 
        for(int i = 0; i < 10; ++i)
        {
            while(!L[i].empty())
            {
                a[j++] = L[i].front();
                L[i].pop_front();
            }
        } 
            
        r = r * 10;
    }
        
} 


int main()
{
    int n;
    int a[100010];
    while (cin >> n)
    {
        for(int i = 0; i < n; ++i)
            cin >> a[i];
        radixSort(a, n);
        for(int i = 0; i < n; ++i)
        {
            cout << a[i] << ' ';
        }  
        cout << endl;
    }

    return 0;
}