基數排序_RADIXSORT
- 基數排序的思想
- 基數排序算法實作
  - 基于計數排序的基數排序
  - 基于最優桶排序的基數排序

基數排序_RADIXSORT

基數排序是一種基于計數排序_COUNTINGSORT或者是最優桶排序(當然也可以基于其他排序算法，隻不過計數排序對于基數排序來說應該是最快的了，因為二者的拼音都是

jishupaixu

,哈哈)的一種可以線上性時間 O(n) 完成的排序算法。部落客在做基數排序的功課的時候，發現有些博文裡面寫到

基數排序

就是

桶排序

，我覺得基數排序和桶排序是不同的，雖然二者都用到了桶的思想，但是二者在桶裡面做的事情是完全不一樣的：

基數排序隻是借用十隻桶來為0-9這十個基數進行排序分堆（可以說是最優的桶排序），反複的在保持穩定的情況下，對個位，十位。。。分别進行桶排序
而桶排序裡面的桶不一定是十個桶，可以是任意多的桶，隻是桶的數量會影響排序的速度，桶排序主要是将元素映射到桶裡面，再在各個桶裡面進行排序，最後再将各個桶裡面的數組歸并在一起(我們将會在後面的文章介紹桶排序)

對于一般的排序算法來說，都是通過元素和元素之間的大小比較來決定元素的大小順序的，這類算法在最差情況至少也要花費 O(nlogn) .但是是對于基數排序來說并不是這樣做的，在基數排序裡面可以說一次元素與元素之間的比較都沒有，都是通過統計數組裡面的元素個數來實作的。

基數排序的思想

基數排序的思想其實很簡單，就是對序列中的各個數首先以個位為排序依據對各個數字進行排序，然後再以十位為排序依據對各個數進行排序，以此類推，将所有位都進行排序，那麼最後得到的序列就是有序序列。

問題一:要是各個數的位數不一樣長怎麼辦？比如有些數字最大十位，有些數字最大百位

答案：以序列中位數最長的為基準，位數不夠的補零，比如位數最高為百位，那麼數字45就補零為045

問題2：為什麼不從高位開始來排序，而是從個位開始排序

答案：因為數位越高，說明占有的比重就越高，個位的排序是為了決定在十位相同的情況下，各個數的順序，而十位的排序就可以直接忽略個位的排序，十位的排序是為了決定在百位相同的情況下，各個數的位置

假設我們有這樣一個序列：

913 75 794 629 48 375 958 630 190 632

現在我們對其進行基數排序

步驟一:對各個數進行補齊

913 075 794 629 048 375 958 630 190 632

步驟二：對個位進行排序

630 190 632 913 794 075 375 048 958 629

步驟三：對十位進行排序

913 629 630 632 048 958 075 375 190 794

步驟三：對百位進行排序

048 075 190 375 629 630 632 794 913 958

ok,上面分析了基數排序的過程，我們知道就是逐位進行排序就可以啦，但是具體要怎麼排才最快呢？

冒泡排序

，

插入排序

，

快速排序

。。。其實這些排序對于一般的輸入數組來說速度是比較快的，但是别忘了這裡有一個限定條件，那就是我們需要排序的數是的區間是在 [0,9] 之間的，那麼自然就是計數排序啦，或者是最優的桶排序(有十個桶)。下面我們用兩種方法分别實作這兩種排序

基數排序算法實作

下面的是基于計數排序和最優桶排序的代碼實作。你可以在這裡下載下傳到完整的源碼：

《基數排序_RADIXSORT》:http://download.csdn.net/detail/ii1245712564/8717167

基于計數排序的基數排序

計數排序的代碼

/**
 * 基數排序
 * @param array     輸入要排序的數組
 * @param minEle    最小元素
 * @param maxEle    最大元素    
 * @param arraySize 數組大小
 * @param radix     基于個位十位還是百位等等排序
 */
void countingSort(int array[] , int minEle , int maxEle , int arraySize , int radix)
{
    if(array == NULL ||\
       minEle > maxEle ||\
       arraySize <  ||\
       radix < )
        return;
    // 建立一個臨時計數數組
    const int & countArraySize = maxEle-minEle+;
    int countArray[countArraySize];
    // 初始化計數數組
    for (int i = ; i < countArraySize; ++i)
    {
        countArray[i] = ;
    }
    // 建立一個臨時的輸出數組,用來存儲輸出排序的結果
    int sortedArray[arraySize];

    // 周遊一遍數組數組，統計各個元素對應的radix的數量
    for (int i = ; i < arraySize; ++i)
    {
        countArray[array[i]%radix/(radix/)]++;
    }

    // 統計比一個元素小的元素個數
    for (int i = ; i < countArraySize; ++i)
    {
        countArray[i] = countArray[i] + countArray[i-];
    }

    // 将元素放入sortedArray裡面合适的位置
    for (int i = arraySize-; i >=; --i)
    {
        sortedArray[countArray[array[i]%radix/(radix/)] - ] = array[i];
        countArray[array[i]%radix/(radix/)]--;
    }

    // 将元素複制回去,感覺這裡有點慢，可不可以進行原址排序？
    for (int i = arraySize-; i >=; --i)
    {
        array[i] = sortedArray[i];
    }
    return;
}

這裡函數接口裡面傳入一個

radix

參數,這個

radix

參數隻能是10的倍數的數字，

array[i]%radix/(radix/10)

則是取出對應位的數字

基數排序代碼

/**
 * 基數排序
 * @param array     輸入的數組
 * @param arraySize 數組大小
 * @param maxRadix  數組裡面元素的最大位
 * @param minRadix  數組裡面元素的最小位
 */
void radixSort(int array[] , int arraySize , int minRadix  ,  int maxRadix)
{
    if(array == NULL || arraySize <  || maxRadix <=  || minRadix <= || minRadix > maxRadix)
        return;
    // 得到基數開始位置
    int tempRadix = ;
    for (int i = ; i < minRadix; ++i)
    {
        tempRadix *= ;
    }
    // 開始進行排序
    for (int i = minRadix; i < maxRadix ; ++i)
    {
        tempRadix *= ;
        countingSort(array ,  ,  , arraySize , tempRadix);
        cout<<tempRadix<<" -----------"<<endl;
        printArray(array , arraySize);
    }
    return;
}

在基數排序裡面調用計數排序為各個位進行排序

main函數代碼

int main(int argc, char const *argv[])
{
    const int & arraySize = ;
    int inArray[arraySize];
    srand((int)(time(NULL)));
    for (int i = ; i < arraySize; ++i)
    {
        inArray[i] = rand()%;
    }
    cout<<"before sort array :"<<endl;
    printArray(inArray , arraySize);

    radixSort(inArray , arraySize ,  ,);
    cout<<"after sort array"<<endl;
    printArray(inArray , arraySize);
    while();
    return ;
}

運作結果：

before sort array :

856 365 404 162 279 512 547 665 70 298

10 ———–

70 162 512 404 365 665 856 547 298 279

100 ———–

404 512 547 856 162 365 665 70 279 298

after sort array

404 512 547 856 162 365 665 70 279 298

基于最優桶排序的基數排序

桶排序代碼

// 定義桶排序的映射函數
#define BUCKET(i) (i)
// 定義十隻桶
const int & bucketNumber = ;

/** some code */
/**
 * 桶排序
 * @param inArray 數組數組
 * @param arraySize 數組大小
 * @param radix   對應的基數,隻能是10的倍數
 */
void bucketSort(int inArray[] , int arraySize , int radix)
{
    if(inArray == NULL || arraySize <  ||radix< ||radix%!=)
        return;
    /** 建立桶 */
    std::vector<int> buckets[bucketNumber];
    /** 将輸入數組裡面的數分類放到桶裡面 */
    for (int i = ; i < arraySize; ++i)
    {
        buckets[BUCKET(inArray[i]%radix/(radix/))].push_back(inArray[i]);
    }
    /** 将桶裡面的數組按順序組合起來 */
    int arrayPos = ;
    for (int i = ; i < bucketNumber && arrayPos < arraySize; ++i)
    {
        std::vector<int> & tempVec = buckets[i];
        for (std::vector<int>::iterator iter = tempVec.begin(); iter != tempVec.end(); ++iter)
        {   
            inArray[arrayPos++] = *iter;
        }
    }
}

這裡桶排序的映射函數

BUCKET(i)

就是映射到

本身，也就是有n個數字，那麼就建立n個桶，這是速度最快的桶排序，同時也是最浪費空間的桶排序。這裡輸入的

radix

隻能是10的倍數

基數排序代碼

/**
 * 基數排序
 * @param inArray   輸入的數組   
 * @param arraySize 數組大小
 */
void radixSort(int inArray[] , int arraySize , int maxPlace)
{
    if(inArray == NULL || arraySize<  || maxPlace < )
        return;
    int radixBasic=;
    for (int i = ; i < maxPlace; ++i)
    {
        radixBasic*=;
        bucketSort(inArray , arraySize , radixBasic);
        cout<<radixBasic<<" -----------"<<endl;
        printArray(inArray,arraySize);
    }
    return;
}

main函數代碼

int main(int argc, char const *argv[])
{
    const int & arraySize = ;
    int inArray[arraySize];
    srand((int)(time(NULL)));
    for (int i = ; i < arraySize; ++i)
    {
        inArray[i] = rand()%;
    }
    cout<<"before sort array :"<<endl;
    printArray(inArray , arraySize);

    radixSort(inArray , arraySize , );
    cout<<"after sort array"<<endl;
    printArray(inArray , arraySize);
    return ;
}

輸出結果：

before sort array :

74 864 595 545 957 804 194 942 454 892

10 ———–

942 892 74 864 804 194 454 595 545 957

100 ———–

804 942 545 454 957 864 74 892 194 595

1000 ———–

74 194 454 545 595 804 864 892 942 957

after sort array

74 194 454 545 595 804 864 892 942 957

基數排序_RADIXSORT基數排序_RADIXSORT

基數排序_RADIXSORT

基數排序的思想

基數排序算法實作

基于計數排序的基數排序

基于最優桶排序的基數排序

繼續閱讀

swmm與lisflood-fp源碼如何一起編譯 CMake指令

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

hdu7108哈希