基數排序

前言

基數排序的排序原理不難理解，但是在演算法設計上，個人感覺還是比那些常見的排序要難的，耐心慢慢一步步理解，還是比較容易看懂的，註意基數排序有兩種，一種是高位優先，一種是低位優先，在這裡我只講低位優先，即先排個位，再排十位……….

時間複雜度

基數排序的時間複雜度為O (nlog(r)m)，其中r為所採取的基數，而m為堆數

排序原理

排序數字為16,21,5,49,33,456,327,56,65,234

這是我測試的實例數字，下麵有源程式，最高位有三位（程式里max=3）,所以要進行三遍排序（下圖只排了兩次，第三遍也一樣啦），第一遍，以個位數分桶，個位相同放在一個桶里，然後把桶里的數在依次拿出來，第一次拿出，順序為21，33，234，5，65，16，456，56，327，49   同理第二遍以十位數字比較，把第一遍拿出的數字再放進桶中，三次迴圈得到結果。

該排序實例，是按部就班的按照桶來放的，但是由於在排序過程中用到的桶是二維數組，因此造成一定的資源浪費，但二維數組前一個數字表示桶號，後一個表示放的位置，極大的降低了理解難度，因為每個桶內放的個數是用count數組存儲，便於從桶內相應位置取出數字。

c++

該排序實例，是按部就班的按照桶來放的，但是由於在排序過程中用到的桶是二維數組，因此造成一定的資源浪費，但二維數組前一個數字表示桶號，後一個表示放的位置，極大的降低了理解難度，因為每個桶內放的個數是用count數組存儲，便於從桶內相應位置取出數字。

#include<iostream>
using namespace std;
int max(int date[],int n){//此函數用於求解所給數組中最大數有幾位
    int max=0;
    for(int i=0;i<n;i++){
        int count=1,tem=date[i];
        while(tem/10!=0){//計算每個數的位數，用count計數
            tem=tem/10;
            count++;
        }
        if(count>max)
            max=count;//把最大位數賦值max
    }
    return max;
}
void basesort(int date[],int n){
    int maxx=max(date,n);//取得最大位數
    int num=1;
    for(int i=0;i<maxx;i++){//位數決定排序迴圈次數
        int count[10];//聲明count為了統計每個桶放了幾個數
        int temp[10]['n'];//temp相當於桶，前一個數標記第幾個籃子，後一個為了標記放的個數
        for(int f=0;f<10;f++){//對聲明數組初始化
            count[f]=0;
        }
        for(int g=0;g<10;g++){//對聲明數組初始化
            for(int z=0;z<n;z++){
                temp[g][z]=0;
            }
        }
        for(int j=0;j<n;j++){
            int fg=date[j]/num;//num是變數，因為每次迴圈比較的位是不同的
            int k=fg%10;
            count[k]++;
            int te=count[k]-1;
            temp[k][te]=date[j];//把數據放k桶的te位上存儲
        }
        int b=0;
        for(int h=0;h<10;h++){
            if(count[h]>0){//h>0說明h桶內有數字存儲
                for(int v=0;v<count[h];v++){//count[h]是h桶的存儲個數
                    date[b]=temp[h][v];//把桶內排好的數全都倒給要排序的數組，進行下輪排序
                    b++;
                }
            }
        }
        num=num*10;
    }
}
 
void print(int date[],int n){//列印排好序的數組
    for(int i=0;i<10;i++){
        cout<<date[i]<<" ";
    }
    cout<<endl;
}
int main() {
    int date[10]={16,21,5,49,33,456,327,56,65,234};
    basesort(date,10);
    print(date,10);
    return 0;
}

運行截圖