桶排序的簡單理解

• 2022 年 6 月 30 日
• 筆記
• 排序, 數據結構與演算法, 演算法

詳細描述

桶排序的工作原理是，將序列中的元素分配到有限的桶里，每個桶再分別進行排序（使用別的排序演算法或者遞歸使用桶排序），最終合併成結果序列。

桶排序詳細的執行步驟如下：

1. 找出序列中最小的元素和最大的元素，並計算得到差值範圍和映射範圍，確定桶的數量；
2. 遍歷整個序列，將每一個元素移動到對應的桶中；
3. 對每一個桶中的元素進行排序，直到所有的桶中元素都有序；
4. 合併每一個桶中的元素成為有序序列。

演算法圖解

問題解疑

桶排序的關鍵是什麼？

桶排序過程中存在兩個關鍵環節：元素到桶的映射規則、排序演算法選擇。

對於映射規則，如果規則設計過於模糊、寬泛，可能所有元素都映射到同一個桶，導致桶排序往比較類排序演算法演變；如果規則設計過於嚴苛，可能每一個桶只分配到一個元素，導致桶排序往計數排序方式演變。

對於桶中元素的排序，可以繼續使用桶排序或者其他排序演算法，最終桶排序的複雜度和穩定性，都根據排序演算法的選擇有所不同。

桶排序的適用於什麼場景？

最好時間複雜度的場景是：序列中的元素值範圍越小越好，比如對範圍只有 10 的序列做排序，申請 10 個桶就能實現遍歷一次序列完成排序。

最好空間複雜度的場景是：序列中的元素值均勻分布，最終分配到每一個桶的元素數量都相差不大，這樣可以避免數據傾斜的問題。

程式碼實現

package cn.fatedeity.algorithm.sort;

import java.util.ArrayList;
import java.util.List;

/**
 * 桶排序演算法
 */
public class BucketSort {
    private static void swap(List<Integer> numbers, int src, int target) {
        int temp = numbers.get(src);
        numbers.set(src, numbers.get(target));
        numbers.set(target, temp);
    }

    private static void insertSort(List<Integer> numbers) {
        for (int i = 1; i < numbers.size(); i++) {
            for (int j = i; j > 0; j--) {
                if (numbers.get(j - 1) <= numbers.get(j)) {
                    break;
                }
                swap(numbers, j, j - 1);
            }
        }
    }

    public static int[] sort(int[] numbers) {
        if (numbers.length == 0) {
            return numbers;
        }

        int min = numbers[0], max = numbers[0];
        for (int number : numbers) {
            if (number < min) {
                min = number;
            } else if (number > max) {
                max = number;
            }
        }

        // 以 10 為步長
        int bucketNum = (max - min) / 10 + 1;
        List<List<Integer>> bucketList = new ArrayList<>();
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new ArrayList<>());
        }

        // 將元素分配到桶中
        for (int number : numbers) {
            int index = (number - min) / 10;
            List<Integer> bucket = bucketList.get(index);
            bucket.add(number);
        }

        int index = 0;
        for (int i = 0; i < bucketNum; i++) {
            List<Integer> bucket = bucketList.get(i);
            insertSort(bucket);
            for (int number : bucket) {
                numbers[index++] = number;
            }
        }
        return numbers;
    }
}