基數(shù)排序知識(shí)點(diǎn)全面概括

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

在基數(shù)排序中，我們不能再只用一位數(shù)的序列來(lái)列舉示例了。一位數(shù)的序列對(duì)基數(shù)排序來(lái)說(shuō)就是一個(gè)計(jì)數(shù)排序。

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

排序原理

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

計(jì)數(shù)排序

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

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

首先初始化數(shù)組 hashArray［］ 為一個(gè)全零數(shù)組。當(dāng)然，在 Java 里，這一步就不需要了，因?yàn)槟J(rèn)就是零了。

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

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

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

基數(shù)排序原理圖

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

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

算法優(yōu)化

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

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

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

算法實(shí)現(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)計(jì)將數(shù)組中的數(shù)字分配到桶中后，各個(gè)桶中的數(shù)字個(gè)數(shù)

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

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

}

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

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

}

/*

* 一個(gè)數(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;

}

/*

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

*

* @param number

* @return

*/

private int length（int number） {

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

}

/*

* 獲取 x 這個(gè)數(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ù)排序過(guò)程圖

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

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

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

復(fù)雜度分析

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

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