五分鐘看懂一個有意思的排序:桶排序

由於LeetCode上的算法題很多涉及到一些基礎的數據結構,為了更好的理解後續更新的一些複雜題目的動畫,推出一個新系列 -----《圖解數據結構》,主要使用動畫來描述常見的數據結構和算法。本系列包括十大排序、堆、隊列、樹、並查集、圖等等大概幾十篇。

桶排序

桶排序(Bucket sort)是一種基於計數的排序算法(計數排序可參考上節的內容),工作的原理是將數據分到有限數量的桶子裏,然後每個桶再分別排序(有可能再使用別的排序算法或是以遞迴方式繼續使用桶排序進行排序)

算法步驟

  1. 設置固定數量的空桶。

  2. 把數據放到對應的桶中。

  3. 對每個不為空的桶中數據進行排序。

  4. 拼接不為空的桶中數據,得到結果。

算法演示

動畫演示GIF加載有點慢,請稍等片刻^_^

imageimage

排序動畫過程解釋

  1. 首先,設置固定數量的空桶,在這裏為了方便演示,設置桶的數量為 5 個空桶

  2. 遍歷整個數列,找到最大值為 56 ,最小值為 2 ,每個桶的範圍為 ( 56 - 2 + 1 )/ 5 = 11

  3. 再次遍歷整個數列,按照公式 floor((數字 – 最小值) / 11) 將數字放到對應的桶中

  4. 比如,數字 7 代入公式 floor((7 – 2) / 11) = 0 放入 0 號桶

  5. 數字 12 代入公式 floor((12 – 2) / 11) = 0 放入 0 號桶

  6. 數字 56 代入公式 floor((56 – 2) / 11) = 4 放入 4 號桶

  7. 當向同一個索引的桶,第二次插入數據時,判斷桶中已存在的數字與新插入數字的大小,按照左到右,從小到大的順序插入(可以使用前面講解的插入排序)實現

  8. 比如,插入數字 19 時, 1 號桶中已經有數字 23 ,在這裏使用插入排序,讓 19 排在 23 前面

  9. 遍歷完整個數列後,合併非空的桶,按從左到右的順序合併0,1,2,3,4桶。

  10. 這樣就完成了 桶排序

代碼實現

為了更好的讓讀者用自己熟悉的編程語言來理解動畫,筆者將貼出多種編程語言的參考代碼,代碼全部來源於網上。

C++代碼實現

imageimage

Java代碼實現

imageimage

JavaScript代碼實現

imageimage

關鍵詞:排序 數字 數據 插入 算法 代碼 使用 動畫 實現 公式

相關推薦:

十大經典排序算法動畫,看我就夠了!

這些奇葩的排序算法,你沒見過動畫吧?

看完動畫你還會不懂 快速排序麼

面試 12:玩轉 Java 快速排序

數據結構與算法(1)——數組與鏈表

『編程題全隊』團隊作業9---項目驗收與總結

數據結構常見的八大排序算法(詳細整理)

學習:排序算法

(轉載) 常見數據結構與算法總結---數據結構