介紹
桶排序可以說得上是最簡單的排序算法了，但是它的使用范圍非常狹窄啊片，不過不可否認的是在其適用范圍內(nèi)涛浙，它的性能要比快速排序還要快上很多倍。
沒錯然磷，桶排序也是一種非比較型排序算法郑趁，這也正是它能夠超越快速排序的原因。
桶排序主要有以下缺陷：
- 參與排序的數(shù)組存放的必須是整數(shù)姿搜。
- 數(shù)組中的最大數(shù)和最小數(shù)保持在一個合理的間距內(nèi)寡润。
- 需要額外的內(nèi)存空間。
下面將通過一個例子講解桶排序的核心思想：
假如說我們需要對全國高考語文成績進行排序舅柜，由于總分只有 150 分梭纹，而且所有的值都在 [0, 150] 之間，所以我們可以申請一個大小為 151 的輔助數(shù)組致份。
var countArray = [];
for(var i = 0; i <= 150; i++) {
countArray[i] = 0;
}
首先我們將數(shù)組的值都置為 0变抽。然后我們以各考生的成績?yōu)橄聵诉f增輔助數(shù)組的值。比如說一個考生成績?yōu)?90知举，那么我們就讓 countArray[90]++瞬沦，這樣一直運算下去，直到所有的考生成績都被遍歷完雇锡，我們就可以統(tǒng)計出來每個分數(shù)有多少考生逛钻，然后再將輔助數(shù)組中的值復制回原數(shù)組，整個數(shù)組自然而然就有序了锰提！
實現(xiàn)
大概了解了桶排序的思想曙痘，下面就來實現(xiàn)一下，假說某年參加高考的學生共有 500 萬人立肘，我們對其語文成績進行排序边坤。
下面是排序代碼：
function countSort(array, k) {
var length = array.length,
countArray = [],
i;
for (i = 0; i < k; i++) {
countArray[i] = 0;
}
for (i = 0; i < length; i++) {
countArray[array[i]]++;
}
var z = 0;
for (i = 0; i < k; i++) {
while (countArray[i]-- > 0) {
array[z++] = i;
}
}
}
下面是測試代碼：
var array = [];
for(var i = 0; i < 5000000; i++) {
array.push(Math.floor(Math.random() * 151));
}
console.time();
countSort(array,151);
console.timeEnd();
console.log(array);
以上代碼在我電腦上的運行時間在 23ms 左右，可見谅年，桶排序排序 500萬數(shù)據(jù)的速度是如此之快茧痒，而我用快速排序?qū)ν粋€數(shù)組進行排序，花了 320 ms 左右融蹂。
所以旺订，如果在合適的時機選擇桶排序弄企，將節(jié)省很多時間。
改進
看了以上代碼也許你發(fā)現(xiàn)了区拳，上述代碼如果排序一個數(shù)值在 [10000, 10200] 范圍內(nèi)的數(shù)組的話拘领，將申請大量的內(nèi)存，為了節(jié)省內(nèi)存樱调，我們不得不改進這個算法约素，讓其適應指定范圍內(nèi)排序。
很簡單的笆凌，我們可以在方法中設置一個 low 和 max 參數(shù)圣猎，就可以靈活自如了。
function countSort(array, low, max) {
var length = array.length,
countArray = [],
i,
k = max - low + 1;
for (i = 0; i < k; i++) {
countArray[i] = 0;
}
for (i = 0; i < length; i++) {
countArray[array[i] - low]++;
}
var z = 0;
for (i = 0; i < k; i++) {
while (countArray[i]-- > 0) {
array[z++] = i + low;
}
}
console.log(countArray.length);
}
總結(jié)
最近一直在學習排序算法菩颖，發(fā)現(xiàn)比較型算法雖然速度比較慢一些(比較型算法的下限是 O(NlogN))样漆，但是適用范圍很廣。非比較型算法雖然使用范圍很有限晦闰，但是其速度非常之快。所以在選擇排序算法時鳍怨，根據(jù)程序的數(shù)值類型以及范圍呻右，首先要考慮是否能夠使用非比較型算法，如果不可以再選用比較型算法鞋喇，比如快速排序声滥。
我已經(jīng)將我寫過的排序算法的代碼全部放到了 我的 Github, 如果有興趣可以前去閱覽一下。
