1、基本思想

基數(shù)排序(Radix Sort)是在桶排序的基礎上發(fā)展而來的，兩種排序都是分配排序的高級實現(xiàn)。分配排序(Distributive Sort)的基本思想：排序過程無須比較關鍵字，而是通過“分配”和“收集”過程來實現(xiàn)排序。它們的時間復雜度可達到線性階：O(n)。

1.1 桶排序

先來看一下桶排序(Bucket Sort)。

1.png

桶排序也稱為箱排序(Bin Sort)，其基本思想是：設置若干個桶，依次掃描待排序的記錄R[0]，R[1]，…，R[n-1]，把關鍵字在某個范圍內(nèi)的記錄全都裝入到第k個桶里(分配)，然后按序號依次將各非空的桶首尾連接起來(收集)。

例如，要將一副混洗的52張撲克牌按點數(shù)A<2<…<J<Q<K排序，需設置13個“桶”，排序時依次將每張牌按點數(shù)放入相應的桶里，然后依次將這些桶首尾相接，就得到了按點數(shù)遞增序排列的一副牌。

桶排序中，桶的個數(shù)取決于關鍵字的取值范圍。因此桶排序要求關鍵字的類型是有限類型，否則可能要無限個桶。

一般情況下每個桶中存放多少個關鍵字相同的記錄是無法預料的，故桶的類型應設計成鏈表為宜。

為保證排序是穩(wěn)定的，分配過程中裝箱及收集過程中的連接必須按先進先出原則進行。

對于桶排序來說，分配過程的時間是O(n)；收集過程的時間為O(m) （采用鏈表來存儲輸入的待排序記錄）或O(m+n)。因此，桶排序的時間為O(m+n)。若桶個數(shù)m的數(shù)量級為O(n)，則桶排序的時間是線性的，即O(n)。

前面說的幾大排序算法 ，大部分時間復雜度都是O(n2)，也有部分排序算法時間復雜度是O(nlogn)。而桶式排序卻能實現(xiàn)O(n)的時間復雜度。但桶排序的缺點是：首先是空間復雜度比較高，需要的額外開銷大。排序有兩個數(shù)組的空間開銷，一個存放待排序數(shù)組，一個就是所謂的桶，比如待排序值是從0到m-1，那就需要m個桶，這個桶數(shù)組就要至少m個空間。其次待排序的元素都要在一定的范圍內(nèi)等等。

1.2 基數(shù)排序

基數(shù)排序是對桶排序的一種改進，這種改進是讓“桶排序”適合于更大的元素值集合的情況，而不是提高性能。

我們還是用撲克牌的例子來說明。一張牌有兩個關鍵字組成：花色(桃<心<梅<方)+面值(A<2<3<4<...<K)。假如一張牌的大小首先被花色決定，同花色的牌有數(shù)字決定的話。我們就有兩種算法來解決這個問題。

即兩張牌，若花色不同，不論面值怎樣，花色低的那張牌小于花色高的，只有在同花色情況下，大小關系才由面值的大小確定。這就是多關鍵碼排序。

為得到排序結果，我們討論兩種排序方法。

• 方法1：先對花色排序，將其分為4 個組，即梅花組、方塊組、紅心組、黑心組。再對每個組分別按面值進行排序，最后，將4 個組連接起來即可。
• 方法2：先按13 個面值給出13 個編號組(2 號，3 號，...，A 號)，將牌按面值依次放入對應的編號組，分成13 堆。再按花色給出4 個編號組(梅花、方塊、紅心、黑心)，將2號組中牌取出分別放入對應花色組，再將3 號組中牌取出分別放入對應花色組，……，這樣，4 個花色組中均按面值有序，然后，將4 個花色組依次連接起來即可。

多關鍵碼排序按照從最主位關鍵碼到最次位關鍵碼或從最次位到最主位關鍵碼的順序逐次排序，分兩種方法：

最高位優(yōu)先(Most Significant Digit first)法，簡稱MSD法：

• 先按k1 排序分組，將序列分成若干子序列，同一組序列的記錄中，關鍵碼k1 相等。
• 再對各組按k2 排序分成子組，之后，對后面的關鍵碼繼續(xù)這樣的排序分組，直到按最次位關鍵碼kd 對各子組排序后。
• 再將各組連接起來，便得到一個有序序列。撲克牌按花色、面值排序中介紹的方法一即是MSD 法。

最低位優(yōu)先(Least Significant Digit first)法，簡稱LSD 法：

• 先從kd 開始排序，再對kd-1進行排序，依次重復，直到按k1排序分組分成最小的子序列后。
• 最后將各個子序列連接起來，便可得到一個有序的序列，撲克牌按花色、面值排序中介紹的方法二即是LSD 法。

對數(shù)字型或字符型的單關鍵字，可以看作由多個數(shù)位或多個字符構成的多關鍵字，此時可以采用“分配-收集”的方法進行排序，這一過程稱作基數(shù)排序法，其中每個數(shù)字或字符可能的取值個數(shù)稱為基數(shù)。比如，撲克牌的花色基數(shù)為4，面值基數(shù)為13。在整理撲克牌時，既可以先按花色整理，也可以先按面值整理。按花色整理時，先按紅、黑、方、花的順序分成4摞（分配），再按此順序再疊放在一起（收集），然后按面值的順序分成13摞（分配），再按此順序疊放在一起（收集），如此進行二次分配和收集即可將撲克牌排列有序。

在“分配-收集”的過程中，需要保證排序的穩(wěn)定性。

基數(shù)排序的思想就是將待排數(shù)據(jù)中的每組關鍵字依次進行桶分配。比如下面的待排序列：

135、242、192、93、345、11、24、19

我們將每個數(shù)值的個位，十位，百位分成三個關鍵字，例如：

135 -> k1(個位)=5 ，k2(十位)=3 ，k3(百位)=1

2.png

然后從最低位個位開始(從最次關鍵字開始)，對所有數(shù)據(jù)的k1關鍵字進行桶分配(因為，每個數(shù)字都是 0-9的，因此桶大小為10)，再依次輸出桶中的數(shù)據(jù)得到下面的序列。

(11)、(242、192)、(93)、(24)、(135、345)、(19)（從最次關鍵字開始排序，忽略百位與十位，按照個位上的數(shù)字分配）

再對上面的序列接著進行針對k2的桶分配，輸出序列為：

(11、19)、(24)、(135)、(242、345)、(192、93)（參考最次關鍵字來排序第二次關鍵字，忽略百位與個位，按照十位上的數(shù)字分配）

最后針對k3的桶分配，輸出序列為：

(011、019、024、093)、(135、192)、(242)、(345)（參考第二次關鍵字來排序最高關鍵字，忽略十位與個位，按照百位上的數(shù)字分配）

排序完畢。

2、實例

    public void radixSort() {

        int max = array[0];
        for (int i = 0; i < array.length; i++) { // 找到數(shù)組中的最大值
            if (array[i] > max) {
                max = array[i];
            }
        }

        int keysNum = 0; // 關鍵字的個數(shù)，我們使用個位、十位、百位...當做關鍵字，所以關鍵字的個數(shù)就是最大值的位數(shù)
        while (max > 0) {
            max /= 10;
            keysNum++;
        }

        List<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < 10; i++) { // 每位可能的數(shù)字為0~9，所以設置10個桶
            buckets.add(new ArrayList<Integer>()); // 桶由ArrayList<Integer>構成
        }

        for (int i = 0; i < keysNum; i++) { // 由最次關鍵字開始，依次按照關鍵字進行分配

            for (int j = 0; j < array.length; j++) { // 掃描所有數(shù)組元素，將元素分配到對應的桶中
                // 取出該元素對應第i+1位上的數(shù)字，比如258，現(xiàn)在要取出十位上的數(shù)字，258%100=58,58/10=5
                int key = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                buckets.get(key).add(array[j]); // 將該元素放入關鍵字為key的桶中
            }

            // 分配完之后，將桶中的元素依次復制回數(shù)組
            int counter = 0; // 元素計數(shù)器
            for (int j = 0; j < 10; j++) {
                ArrayList<Integer> bucket = buckets.get(j); // 關鍵字為j的桶
                while (bucket.size() > 0) {
                    array[counter++] = bucket.remove(0); // 將桶中的第一個元素復制到數(shù)組，并移除
                }
            }
            System.out.print("第" + (i + 1) + "輪排序：");
            display();
        }

    }

打印結果如下：

3.png

3、算法分析

初看起來，基數(shù)排序的執(zhí)行效率似乎好的讓人無法相信，所有要做的只是把原始數(shù)據(jù)項從數(shù)組復制到鏈表，然后再復制回去。如果有10個數(shù)據(jù)項，則有20次復制，對每一位重復一次這個過程。假設對5位的數(shù)字排序，就需要20 * 5=100次復制。

*如果有100個數(shù)據(jù)項，那么就有200 * 5=1000次復制。復制的次數(shù)與數(shù)據(jù)項的個數(shù)成正比，即O(n)。這是我們看到的效率最高的排序算法。

不幸的是，數(shù)據(jù)項越多，就需要更長的關鍵字，如果數(shù)據(jù)項增加10倍，那么關鍵字必須增加一位（多一輪排序）。復制的次數(shù)和數(shù)據(jù)項的個數(shù)與關鍵字長度成正比，可以認為關鍵字長度是N的對數(shù)。因此在大多數(shù)情況下，基數(shù)排序的執(zhí)行效率倒退為O(N*logN)，和快速排序差不多。

4、排序算法總結

4.1 穩(wěn)定性即復雜度

八大排序算法的穩(wěn)定性及復雜度總結如下：

4.png

4.2 選擇排序算法準則

每種排序算法都各有優(yōu)缺點。因此，在實用時需根據(jù)不同情況適當選用，甚至可以將多種方法結合起來使用。

影響排序的因素有很多，平均時間復雜度低的算法并不一定就是最優(yōu)的。相反，有時平均時間復雜度高的算法可能更適合某些特殊情況。同時，選擇算法時還得考慮它的可讀性，以利于軟件的維護。一般而言，需要考慮的因素有以下四點：

• 待排序的記錄數(shù)目n的大小；
• 記錄本身數(shù)據(jù)量的大小，也就是記錄中除關鍵字外的其他信息量的大?。?/li>
• 關鍵字的結構及其分布情況；
• 對排序穩(wěn)定性的要求。

設待排序元素的個數(shù)為n。

• 當n較大，則應采用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序。
  快速排序：是目前基于比較的內(nèi)部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
  堆排序：如果內(nèi)存空間允許且要求穩(wěn)定性的，
  歸并排序：它有一定數(shù)量的數(shù)據(jù)移動，所以我們可能過與插入排序組合，先獲得一定長度的序列，然后再合并，在效率上將有所提高。
• 當n較大，內(nèi)存空間允許，且要求穩(wěn)定性，推薦歸并排序
• 當n較小，可采用直接插入或直接選擇排序。
  直接插入排序：當元素分布有序，直接插入排序?qū)⒋蟠鬁p少比較次數(shù)和移動記錄的次數(shù)。
  直接選擇排序 ：元素分布有序，如果不要求穩(wěn)定性，選擇直接選擇排序
• 一般不使用或不直接使用傳統(tǒng)的冒泡排序。
• 基數(shù)排序
  它是一種穩(wěn)定的排序算法，但有一定的局限性：
  　　1、關鍵字可分解。
  　　2、記錄的關鍵字位數(shù)較少，如果密集更好
  　　3、如果是數(shù)字時，最好是無符號的，否則將增加相應的映射復雜度，可先將其正負分開排序。