介紹
桶排序是最簡單的排序算法，舉例說明：有場景下有數(shù)據(jù)范圍是0~n，我們假設(shè)已經(jīng)有n+1個桶用于排序，將需要被排序的數(shù)據(jù)一個個放入對應(yīng)的桶的序號中请契，即數(shù)據(jù) 3被放入第3個桶，數(shù)據(jù)67被放入第67個桶夏醉，一個桶可裝多個數(shù)姚糊；最終從頭到尾（升序）或者從尾到頭（降序）找出桶里的數(shù)據(jù)。
例子
假設(shè)有一個待排序數(shù)組[77, 6, 37, 96, 34, 6,14], 桶排序的js實(shí)現(xiàn)如下(升序)：
function sort(arr){
var buckets = [], //輔助桶
result = []; //用于保存結(jié)果
//待排序數(shù)據(jù)依次放入桶授舟，這里遍歷n次
arr.forEach(function(item){
//一個桶可以裝多個數(shù)救恨，所以用數(shù)組裝
if(buckets[item]) buckets[item].push(item);
else buckets[item] = [item];
});
//將桶里從頭到尾連起來輸出,這里遍歷n次
buckets.forEach(function(item){
if(item) result = result.concat(item);
})
return result;
}
var arr = [77, 6, 37, 96, 34, 6, 14];
console.log(sort(arr)); // =>[6, 6, 14, 34, 37, 77, 96]
時間復(fù)雜度
大O階計算f(n) = n + n = 2n，所以時間復(fù)雜度為O(n)释树。雖然時間上消耗還算ok肠槽，但桶排序有個致命的缺點(diǎn)：浪費(fèi)空間。
感謝閱讀奢啥！歡迎關(guān)注秸仙！持續(xù)更新中...
