拜託,面試別再問我桶排序了
排序,面試中考察基本功問的比較多的問題。
時間複雜度為O(n)的排序,常見的有三種:
-
基數排序 (Radix Sort)
-
計數排序 (Counting Sort)
-
桶排序 (Bucket Sort)
今天,1分鐘,爭取讓大家搞懂 桶排序 。
畫外音:百度“桶排序”,很多文章是錯誤的,本文內容與《演算法導論》中的桶排序保持一致。
桶排序的適用範圍是,待排序的元素能夠 均勻分佈在某一個範圍[MIN, MAX]之間 。
畫外音:很多業務場景是符合這一場景,待排序的元素在某一範圍內,且是均勻分佈的。
桶排序需要兩個輔助空間:
-
第一個輔助空間,是 桶空間 B
-
第二個輔助空間,是 桶內的元素連結串列空間
總的來說,空間複雜度是O(n)。
桶排序有兩個關鍵步驟:
-
掃描待排序資料A[N],對於元素A[i], 放入對應的桶X
-
A[i]放入桶X,如果桶X已經有了若干元素, 使用插入排序,將arr[i]放到桶內合適的位置
畫外音:
(1)桶X內的所有元素,是一直有序的;
(2)插入排序是穩定的,因此桶內元素順序也是穩定的;
當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) 的排序
-
桶排序,是一種 穩定的 排序
-
桶排序,適用於資料均勻分佈在一個區間內的場景
希望這一分鐘,大家有收穫。
架構師之路 -分享 可落地 的技術文章
推薦閱讀:
《 ofollow,noindex">拜託,面試別再問我基數排序了! 》
《 拜託,面試別再問我計數排序了! 》
至此,三種常見的時間複雜度為O(n)的排序演算法介紹完畢。希望面試能幫到大家。