又一個(gè)，時(shí)間復(fù)雜度為O(n)的排序！

桶排序(Bucket Sort)，是一種時(shí)間復(fù)雜度為O(n)的排序。

畫外音：百度“桶排序”，很多文章是錯(cuò)誤的，本文內(nèi)容與《算法導(dǎo)論》中的桶排序保持一致。

?

桶排序的適用范圍是，待排序的元素能夠均勻分布在某一個(gè)范圍[MIN, MAX]之間。

畫外音：很多業(yè)務(wù)場景是符合這一場景，待排序的元素在某一范圍內(nèi)，且是均勻分布的。

?

桶排序需要兩個(gè)輔助空間：

（1）第一個(gè)輔助空間，是桶空間B；

（2）第二個(gè)輔助空間，是桶內(nèi)的元素鏈表空間；

總的來說，空間復(fù)雜度是O(n)。

?

桶排序有兩個(gè)關(guān)鍵步驟：

（1）掃描待排序數(shù)據(jù)A[N]，對(duì)于元素A[i]，放入對(duì)應(yīng)的桶X；

（2）A[i]放入桶X，如果桶X已經(jīng)有了若干元素，使用插入排序，將arr[i]放到桶內(nèi)合適的位置；

畫外音：

（1）桶X內(nèi)的所有元素，是一直有序的；

（2）插入排序是穩(wěn)定的，因此桶內(nèi)元素順序也是穩(wěn)定的；

?

當(dāng)arr[N]中的所有元素，都按照上述步驟放入對(duì)應(yīng)的桶后，就完成了全量的排序。

?

桶排序的偽代碼是：

bucket_sort(A[N]){

? ? ?for i =1 to n{

? ? ? ? ? ?將A[i]放入對(duì)應(yīng)的桶B[X];

? ? ? ? ? ?使用插入排序，將A[i]插入到B[X]中正確的位置;

? ? ?}

? ? ?將B[X]中的所有元素，按順序合并，排序完畢;

}

?

舉個(gè)栗子：

假設(shè)待排序的數(shù)組均勻分布在[0, 99]之間：

{5,18,27,33,42,66,90,8,81,47,13,67,9,36,62,22}

可以設(shè)定10個(gè)桶，申請(qǐng)額外的空間bucket[10]來作為輔助空間。其中，每個(gè)桶bucket[i]來存放[10*i, 10*i+9]的元素鏈表。

上圖所示：

（1）待排序的數(shù)組為unsorted[16]；

（2）桶空間是buket[10]；

（3）掃描所有元素之后，元素被放到了自己對(duì)應(yīng)的桶里；

（4）每個(gè)桶內(nèi)，使用插入排序，保證一直是有序的；

例如，標(biāo)紅的元素66, 67, 62最終會(huì)在一個(gè)桶里，并且使用插入排序桶內(nèi)保持有序。

?

最終，每個(gè)桶按照次序輸出，排序完畢。

?

神奇不神奇！?。?/strong>

?

桶排序(Bucket Sort)，總結(jié)：

（1）桶排序，是一種復(fù)雜度為O(n)的排序；

（2）桶排序，是一種穩(wěn)定的排序；

（3）桶排序，適用于數(shù)據(jù)均勻分布在一個(gè)區(qū)間內(nèi)的場景；

?

希望這一分鐘，大家有收獲。

架構(gòu)師之路-分享可落地的技術(shù)文章

推薦閱讀：

《這一種O(n)的排序算法》

《這個(gè)排序這么酷，為什么知道的人很少？》

《世界上最漂亮的排序算法！》