排序，面試中考察基本功問(wèn)的比較多的問(wèn)題。

時(shí)間復(fù)雜度為O(n)的排序，常見(jiàn)的有三種：

• 基數(shù)排序(Radix Sort)
• 計(jì)數(shù)排序(Counting Sort)
• 桶排序(Bucket Sort)

今天，1分鐘，爭(zhēng)取讓大家搞懂桶排序。

[[248423]]

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

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

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

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

• ***個(gè)輔助空間，是桶空間B
• 第二個(gè)輔助空間，是桶內(nèi)的元素鏈表空間

總的來(lái)說(shuō)，空間復(fù)雜度是O(n)。

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

• 掃描待排序數(shù)據(jù)A[N]，對(duì)于元素A[i]，放入對(duì)應(yīng)的桶X
• A[i]放入桶X，如果桶X已經(jīng)有了若干元素，使用插入排序，將arr[i]放到桶內(nèi)合適的位置

畫(huà)外音：

• 桶X內(nèi)的所有元素，是一直有序的;
• 插入排序是穩(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]來(lái)作為輔助空間。其中，每個(gè)桶bucket[i]來(lái)存放[10*i, 10*i+9]的元素鏈表。

上圖所示：

• 待排序的數(shù)組為unsorted[16]
• 桶空間是buket[10]
• 掃描所有元素之后，元素被放到了自己對(duì)應(yīng)的桶里
• 每個(gè)桶內(nèi)，使用插入排序，保證一直是有序的

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

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

神奇不神奇!!!

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

• 桶排序，是一種復(fù)雜度為O(n)的排序
• 桶排序，是一種穩(wěn)定的排序
• 桶排序，適用于數(shù)據(jù)均勻分布在一個(gè)區(qū)間內(nèi)的場(chǎng)景

【本文為51CTO專欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者】

戳這里，看該作者更多好文