排序，面試中考察基本功問的比較多的問題。

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

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

今天，1分鐘，爭取讓大家搞懂桶排序。

[[248423]]

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

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

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

桶排序需要兩個輔助空間：

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

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

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

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

畫外音：

• 桶X內(nèi)的所有元素，是一直有序的;
• 插入排序是穩(wěn)定的，因此桶內(nèi)元素順序也是穩(wěn)定的;

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

桶排序的偽代碼是：

bucket_sort(A[N]){ 
     for i =1 to n{ 
           將A[i]放入對應(yīng)的桶B[X]; 
           使用插入排序，將A[i]插入到B[X]中正確的位置; 
     } 
     將B[X]中的所有元素，按順序合并，排序完畢; 
} 

舉個栗子：

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

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

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

上圖所示：

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

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

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

神奇不神奇!!!

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

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

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

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