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

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

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

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

[[248423]]

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

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

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

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

• ***個輔助空間，是桶空間B
• 第二個輔助空間，是桶內的元素鏈表空間

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

桶排序有兩個關鍵步驟：

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

畫外音：

• 桶X內的所有元素，是一直有序的;
• 插入排序是穩定的，因此桶內元素順序也是穩定的;

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

桶排序的偽代碼是：

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

舉個栗子：

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

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

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

上圖所示：

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

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

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

神奇不神奇!!!

桶排序(Bucket Sort)，總結：

• 桶排序，是一種復雜度為O(n)的排序
• 桶排序，是一種穩定的排序
• 桶排序，適用于數據均勻分布在一個區間內的場景

【本文為51CTO專欄作者“58沈劍”原創稿件，轉載請聯系原作者】

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