數(shù)據(jù)背景

在基數(shù)排序中，我們不能再只用一位數(shù)的序列來列舉示例了。一位數(shù)的序列對基數(shù)排序來說就是一個計數(shù)排序。

這里我們列舉無序序列 T = ［ 2314， 5428， 373， 2222， 17 ］

排序原理

上面說到基數(shù)排序不需要進行元素的比較與交換。如果你有一些算法的功底，或者豐富的項目經(jīng)驗，我想你可能已經(jīng)想到了這可能類似于一些“打表”或是哈希的做法。而計數(shù)排序則是打表或是哈希思想最簡單的實現(xiàn)。

計數(shù)排序

計數(shù)排序的核心思想是，構(gòu)建一個足夠大的數(shù)組 hashArray［］，數(shù)組大小需要保證能夠把所有元素都包含在這個數(shù)組上 。

假設(shè)我們有無序序列 T = ［ 2314， 5428， 373， 2222， 17 ］

首先初始化數(shù)組 hashArray［］ 為一個全零數(shù)組。當然，在 Java 里，這一步就不需要了，因為默認就是零了。

在對序列 T 進行排序時，只要依次讀取序列 T 中的元素，并修改數(shù)組 hashArray［］ 中把元素值對應(yīng)位置上的值即可。這一句有一些繞口。打個比方，我們要把 T［0］ 映射到 hashArray［］ 中，就是 hashArray［T［0］］ = 1. 也就是 hashArray［2314］ = 1. 如果序列 T 中有兩個相同元素，那么在 hashArray 的相應(yīng)位置上的值就是 2。

下圖是計數(shù)排序的原理圖：

（假設(shè)有無序序列：［ 5， 8， 9， 1， 4， 2， 9， 3， 7， 1， 8， 6， 2， 3， 4， 0， 8 ］）

基數(shù)排序原理圖

上面的計數(shù)排序只是一個引導(dǎo)，好讓你可以循序漸進地了解基數(shù)排序。

上面這幅圖，或許你已經(jīng)在其他的博客里見到過。這是一個很好的引導(dǎo)跟說明。在基數(shù)排序里，我們需要一個很大的二維數(shù)組，二維數(shù)組的大小是 （10 * n）。10 代表的是我們每個元素的每一位都有 10 種可能，也就是 10 進制數(shù)。在上圖中，我們是以每個數(shù)的個位來代表這個數(shù)，于是，5428 就被填充到了第 8 個桶中了。下次再進行填充的時候，就是以十位進行填充，比如 5428 在此時，就會選擇以 2 來代表它。

算法優(yōu)化

在算法的原理中，我們是以一張二維數(shù)組的表來存儲這些無序的元素。使用二維數(shù)組有一個很明顯的不足就是二維數(shù)組太過稀疏。數(shù)組的利用率為 10%。

在尋求優(yōu)化的路上，我們想到一種可以壓縮空間的方法，且時間復(fù)雜度并沒有偏離得太厲害。那就是設(shè)計了兩個輔助數(shù)組，一個是 count［］，一個是 bucket［］。count 用于記錄在某個桶中的最后一個元素的下標，然后再把原數(shù)組中的元素計算一下它應(yīng)該屬于哪個“桶”，并修改相應(yīng)位置的 count 值。直到最大數(shù)的最高位也被添加到桶中，或者說，當所有的元素都被被在第 0 個桶中，基數(shù)排序就結(jié)束了。

優(yōu)化后的原理圖如下：

算法實現(xiàn)

import org.algorithm.array.sort.interf.Sortable;

/**

*

* 基數(shù)排序/桶排序

*

*

* @author Q-WHai

* @see http://blog.csdn.net/lemon_tree12138

* @version 0.1.1

*/

public class RadixSort implements Sortable {

@Override

public int［］ sort（int［］ array） {

if （array == null） {

return null;

}

int maxLength = maxLength（array）;

return sortCore（array， 0， maxLength）;

}

private int［］ sortCore（int［］ array， int digit， int maxLength） {

if （digit >= maxLength） {

return array;

}

final int radix = 10; // 基數(shù)

int arrayLength = array.length;

int［］ count = new int［radix］;

int［］ bucket = new int［arrayLength］;

// 統(tǒng)計將數(shù)組中的數(shù)字分配到桶中后，各個桶中的數(shù)字個數(shù)

for （int i = 0; i < arrayLength; i++） {

count［getDigit（array［i］， digit）］++;

}

// 將各個桶中的數(shù)字個數(shù)，轉(zhuǎn)化成各個桶中最后一個數(shù)字的下標索引

for （int i = 1; i < radix; i++） {

count［i］ = count［i］ + count［i - 1］;

}

// 將原數(shù)組中的數(shù)字分配給輔助數(shù)組 bucket

for （int i = arrayLength - 1; i >= 0; i--） {

int number = array［i］;

int d = getDigit（number， digit）;

bucket［count［d］ - 1］ = number;

count［d］--;

}

return sortCore（bucket， digit + 1， maxLength）;

}

/*

* 一個數(shù)組中最大數(shù)字的位數(shù)

*

* @param array

* @return

*/

private int maxLength（int［］ array） {

int maxLength = 0;

int arrayLength = array.length;

for （int i = 0; i < arrayLength; i++） {

int currentLength = length（array［i］）;

if （maxLength < currentLength） {

maxLength = currentLength;

}

}

return maxLength;

}

/*

* 計算一個數(shù)字共有多少位

*

* @param number

* @return

*/

private int length（int number） {

return String.valueOf（number）.length（）;

}

/*

* 獲取 x 這個數(shù)的 d 位數(shù)上的數(shù)字

* 比如獲取 123 的 0 位數(shù)，結(jié)果返回 3

*

* @param x

* @param d

* @return

*/

private int getDigit（int x， int d） {

int a［］ = { 1， 10， 100， 1000， 10000， 100000， 1000000， 10000000， 100000000， 1000000000 };

return （（x / a［d］） % 10）;

}

}

基數(shù)排序過程圖

如果我們的無序是 T = ［ 2314， 5428， 373， 2222， 17 ］，那么其排序的過程就如下兩幅所示。

基數(shù)排序過程圖-1

基數(shù)排序過程圖-2

復(fù)雜度分析

其中，d 為位數(shù)，r 為基數(shù)，n 為原數(shù)組個數(shù)。

在基數(shù)排序中，因為沒有比較操作，所以在復(fù)雜上，最好的情況與最壞的情況在時間上是一致的，均為 O（d * （n + r））。