什麼是基數排序?

老讀者可能比較熟悉，剛開始的時候寫了一個排序算法系列，把常見的排序算法都寫了，有興趣的可以在公眾號內的目錄菜單欄中選擇數據結構與算法查看。

但是還是有少數的排序算法沒寫，下面的一篇就是。這篇文章用漫畫的形式講解了基數排序，通俗易懂。

—————  第二天  —————

————————————

什麼是計數排序呢？讓我們舉例說明一下。

給定20個隨機整數的值如下：

9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9 ，7，9

如何最快地把這些無序的隨機整數排序？

由於這些整數的範圍是從0到10這11個數，我們可以創建一個長度11的空數組，數組從0到10的下標，對應著待排序的隨機整數值0到10：

接下來遍歷這個無序的隨機數列，每一個整數按照其值對號入座，對應數組下標的元素進行加1操作。

比如第一個整數是9，那麼數組下標為9的元素加1：

第二個整數是3，那麼數組下標為3的元素加1：

繼續遍歷數列並修改數組.

最終，數列遍歷完畢時，數組的狀態如下：

數組每一個下標位置的值，代表了數列中對應整數出現的次數。

有了這個「統計結果」，排序就很簡單了。直接遍歷數組，輸出數組元素的下標值，元素的值是幾，就輸出幾次：

0，1，1，2，3，3，3，4，4，5，5，6，7，7，8，9，9，9，9，10

顯然，這個輸出的數列已經是有序的了。

這就是計數排序的樸素版本。

為了實現穩定排序（排序後，相等元素原本的先後順序不變），真正的計數排序要稍微複雜一些，感興趣的小夥伴可以讀一讀這篇：

漫畫：什麼是計數排序？

計數排序有什麼局限呢？讓我們看兩個特殊的需求：

需求A，為一組給定的手機號排序：

18914021920

13223132981

13566632981

13660891039

13361323035

...

...

按照計數排序的思路，我們要根據手機號的取值範圍，創建一個空數組。

可是，11位手機號有多少種組合？恐怕要建立一個大得不可想像的數組，才能裝下所有可能出現的11位手機號！

需求B，為一組英文單詞排序：

banana

apple

orange

peach

cherry

...

...

計數排序適合的場景是對整數做排序，如果遇到英文單詞，就無能為力了。

如何有效處理諸如手機號、英文單詞等複雜元素的排序呢？僅僅靠一次計數排序很難實現。

這時候，我們不妨把排序工作拆分成多個階段，每一個階段只根據一個字符進行計數排序，一共排序k輪（k是元素長度）。

或許這樣的描述有些抽象，我們來舉一個例子。

數組中有若干個字符串元素，每個字符串元素都是由三個英文字母組成：

bda，cfd，qwe，yui，abc，rrr，uee

如何將這些字符串按照字母順序排序呢？

由於每個字符串的長度是3個字符，我們可以把排序工作拆分成3輪：

第一輪：按照最低位字符排序。排序過程使用計數排序，把字母的ascii碼對應到數組下標，第一輪排序結果如下：

第二輪：在第一輪排序結果的基礎上，按照第二位字符排序。

需要注意的是，這裡使用的計數排序必須是穩定排序，這樣才能保證第一輪排出的先後順序在第二輪還能繼續保持。

比如在第一輪排序後，元素uue在元素yui之前。那麼第二輪排序時，兩者的第二位字符雖然同樣是u，但先後順序萬萬不能變，否則第一輪排序就白做了。

第三輪：在第二輪排序結果的基礎上，按照最高位字符排序。

如此一來，這些字符串的順序就排好了。

像這樣把字符串元素按位拆分，每一位進行一次計數排序的算法，就是基數排序（Radix Sort）。

基數排序既可以從高位優先進行排序（Most Significant Digit first，簡稱MSD），也可以從低位優先進行排序（Least Significant Digit first，簡稱LSD）。

剛才我們所舉的例子，就是典型的LSD方式的基數排序。

什麼意思呢？比如給定如下幾個單詞：

banana

apple

orange

ape

he

這裡最長的單詞有6個字符，其餘不足6個字符的單詞在末尾補0即可：

banana

apple0

orange

ape000

he0000

在排序時，我們把字符0當做是比a更小的字符，排序結果如下：

ape000

apple0

banana

he0000

orange

//ascii碼的取值範圍

public static final int ASCII_RANGE = 128;

public static String[] radixSort(String[] array,int maxLength)

{

//排序結果數組，用於存儲每一次按位排序的臨時結果

String[] sortedArray = new String[array.length];

//從個位開始比較，一直比較到最高位

for(int k=maxLength-1;k>=0;k--)

{

//計數排序的過程，分成三步：

//1.創建輔助排序的統計數組，並把待排序的字符對號入座，

        //這裡為了代碼簡潔，直接使用ascii碼範圍作為數組長度

int[] count = new int[ASCII_RANGE];

for(int i=0;i<array.length;i++)

{

int index = getCharIndex(array[i],k);

count[index]++;

}

//2.統計數組做變形，後面的元素等於前面的元素之和

for(int i=1;i<count.length;i++)

{

count[i] = count[i] + count[i-1];

}

//3.倒序遍歷原始數列，從統計數組找到正確位置，輸出到結果數組

for(int i=array.length-1;i>=0;i--) {

int index = getCharIndex(array[i],k);

int sortedIndex = count[index]-1;

sortedArray[sortedIndex] = array[i];

count[index]--;

}

//下一輪排序需要以上一輪的排序結果為基礎，因此把結果複製給array

array = sortedArray.clone();

}

return array;

}

//獲取字符串第k位字符所對應的ascii碼序號

private static int getCharIndex(String str, int k){

//如果字符串長度小於k，直接返回0，相當於給不存在的位置補0

if(str.length() < k+1){

return 0;

}

return str.charAt(k);

}

public static void main(String[] args)

{

String[] array = {"qd","abc", "qwe","hhh","a","cws", "ope"};

System.out.println(Arrays.toString(radixSort(array, 3)));

}

這段代碼基於一個大循環來實現，循環進行k次，k就是數組中最長字符串元素的字符數。

在循環體內，執行的是計數排序的邏輯。這個穩定的計數排序算法不太好理解，在小灰往期的漫畫中有進行詳細講解（漫畫：什麼是計數排序？）。

—————END—————

讓天下沒有難懂的技術

覺得不錯，點個在看唄