老讀者可能比較熟悉，剛開始的時(shí)候?qū)懥艘粋€(gè)排序算法系列，把常見的排序算法都寫了，有興趣的可以在公眾號(hào)內(nèi)的目錄菜單欄中選擇數(shù)據(jù)結(jié)構(gòu)與算法查看。

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

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

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

什么是計(jì)數(shù)排序呢？讓我們舉例說明一下。

給定20個(gè)隨機(jī)整數(shù)的值如下：

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

如何最快地把這些無序的隨機(jī)整數(shù)排序？

由于這些整數(shù)的范圍是從0到10這11個(gè)數(shù)，我們可以創(chuàng)建一個(gè)長度11的空數(shù)組，數(shù)組從0到10的下標(biāo)，對(duì)應(yīng)著待排序的隨機(jī)整數(shù)值0到10：

接下來遍歷這個(gè)無序的隨機(jī)數(shù)列，每一個(gè)整數(shù)按照其值對(duì)號(hào)入座，對(duì)應(yīng)數(shù)組下標(biāo)的元素進(jìn)行加1操作。

比如第一個(gè)整數(shù)是9，那么數(shù)組下標(biāo)為9的元素加1：

第二個(gè)整數(shù)是3，那么數(shù)組下標(biāo)為3的元素加1：

繼續(xù)遍歷數(shù)列并修改數(shù)組......

最終，數(shù)列遍歷完畢時(shí)，數(shù)組的狀態(tài)如下：

數(shù)組每一個(gè)下標(biāo)位置的值，代表了數(shù)列中對(duì)應(yīng)整數(shù)出現(xiàn)的次數(shù)。

有了這個(gè)“統(tǒng)計(jì)結(jié)果”，排序就很簡(jiǎn)單了。直接遍歷數(shù)組，輸出數(shù)組元素的下標(biāo)值，元素的值是幾，就輸出幾次：

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

顯然，這個(gè)輸出的數(shù)列已經(jīng)是有序的了。

這就是計(jì)數(shù)排序的樸素版本。

為了實(shí)現(xiàn)穩(wěn)定排序(排序后，相等元素原本的先后順序不變)，真正的計(jì)數(shù)排序要稍微復(fù)雜一些，感興趣的小伙伴可以讀一讀這篇：

漫畫：什么是計(jì)數(shù)排序？

計(jì)數(shù)排序有什么局限呢？讓我們看兩個(gè)特殊的需求：

需求A，為一組給定的手機(jī)號(hào)排序：

18914021920

13223132981

13566632981

13660891039

13361323035

........

........

按照計(jì)數(shù)排序的思路，我們要根據(jù)手機(jī)號(hào)的取值范圍，創(chuàng)建一個(gè)空數(shù)組。

可是，11位手機(jī)號(hào)有多少種組合？恐怕要建立一個(gè)大得不可想象的數(shù)組，才能裝下所有可能出現(xiàn)的11位手機(jī)號(hào)！

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

banana

apple

orange

peach

cherry

........

........

計(jì)數(shù)排序適合的場(chǎng)景是對(duì)整數(shù)做排序，如果遇到英文單詞，就無能為力了。

如何有效處理諸如手機(jī)號(hào)、英文單詞等復(fù)雜元素的排序呢？僅僅靠一次計(jì)數(shù)排序很難實(shí)現(xiàn)。

這時(shí)候，我們不妨把排序工作拆分成多個(gè)階段，每一個(gè)階段只根據(jù)一個(gè)字符進(jìn)行計(jì)數(shù)排序，一共排序k輪(k是元素長度)。

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

數(shù)組中有若干個(gè)字符串元素，每個(gè)字符串元素都是由三個(gè)英文字母組成：

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

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

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

第一輪：按照最低位字符排序。排序過程使用計(jì)數(shù)排序，把字母的ascii碼對(duì)應(yīng)到數(shù)組下標(biāo)，第一輪排序結(jié)果如下：

第二輪：在第一輪排序結(jié)果的基礎(chǔ)上，按照第二位字符排序。

需要注意的是，這里使用的計(jì)數(shù)排序必須是穩(wěn)定排序，這樣才能保證第一輪排出的先后順序在第二輪還能繼續(xù)保持。

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

第三輪：在第二輪排序結(jié)果的基礎(chǔ)上，按照最高位字符排序。

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

像這樣把字符串元素按位拆分，每一位進(jìn)行一次計(jì)數(shù)排序的算法，就是基數(shù)排序(Radix Sort)。

基數(shù)排序既可以從高位優(yōu)先進(jìn)行排序(Most Significant Digit first，簡(jiǎn)稱MSD)，也可以從低位優(yōu)先進(jìn)行排序(Least Significant Digit first，簡(jiǎn)稱LSD)。

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

什么意思呢？比如給定如下幾個(gè)單詞：

banana

apple

orange

ape

he

這里最長的單詞有6個(gè)字符，其余不足6個(gè)字符的單詞在末尾補(bǔ)0即可：

banana

apple0

orange

ape000

he0000

在排序時(shí)，我們把字符0當(dāng)做是比a更小的字符，排序結(jié)果如下：

ape000

apple0

banana

he0000

orange

//ascii碼的取值范圍

public static final int ASCII_RANGE = 128;

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

{

//排序結(jié)果數(shù)組，用于存儲(chǔ)每一次按位排序的臨時(shí)結(jié)果

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

//從個(gè)位開始比較，一直比較到最高位

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

{

//計(jì)數(shù)排序的過程，分成三步：

//1.創(chuàng)建輔助排序的統(tǒng)計(jì)數(shù)組，并把待排序的字符對(duì)號(hào)入座，

????????//這里為了代碼簡(jiǎn)潔，直接使用ascii碼范圍作為數(shù)組長度

int[] count = new int[ASCII_RANGE];

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

{

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

count[index]++;

}

//2.統(tǒng)計(jì)數(shù)組做變形，后面的元素等于前面的元素之和

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

{

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

}

//3.倒序遍歷原始數(shù)列，從統(tǒng)計(jì)數(shù)組找到正確位置，輸出到結(jié)果數(shù)組

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]--;

}

//下一輪排序需要以上一輪的排序結(jié)果為基礎(chǔ)，因此把結(jié)果復(fù)制給array

array = sortedArray.clone();

}

return array;

}

//獲取字符串第k位字符所對(duì)應(yīng)的ascii碼序號(hào)

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

//如果字符串長度小于k，直接返回0，相當(dāng)于給不存在的位置補(bǔ)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)));

}

這段代碼基于一個(gè)大循環(huán)來實(shí)現(xiàn)，循環(huán)進(jìn)行k次，k就是數(shù)組中最長字符串元素的字符數(shù)。

在循環(huán)體內(nèi)，執(zhí)行的是計(jì)數(shù)排序的邏輯。這個(gè)穩(wěn)定的計(jì)數(shù)排序算法不太好理解，在小灰往期的漫畫中有進(jìn)行詳細(xì)講解(漫畫：什么是計(jì)數(shù)排序？)。

—————END—————

趣談編程

讓天下沒有難懂的技術(shù)

覺得不錯(cuò)，點(diǎn)個(gè)在看唄

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的problem a: 简单的整数排序_什么是基数排序？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。