Bucket sort - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

入门链接

马士兵说:桶排序-算法思想

图解

bubble_sort

详解

【排序】图解桶排序

标准写法

public static void bucketSort(int[] arr) {

    // 用数组中的最大值和最小值来计算桶的数量
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }

    // 计算桶的数量
    int bucketNum = (max - min) / arr.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for (int i = 0; i < bucketNum; i++) {
        bucketArr.add(new ArrayList<Integer>());
    }

    // 将每个元素放入桶
    for (int i = 0; i < arr.length; i++) {
        // 找到对应的桶
        int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }

    // 对每个桶进行排序
    for (int i = 0; i < bucketArr.size(); i++) {
        // 这里可用别的排序方法,例如归并排序,时间复杂度是nlogn
        Collections.sort(bucketArr.get(i));
    }

    // 将桶中的元素赋值到原序列
    int index = 0;
    for (int i = 0; i < bucketArr.size(); i++) {
        for (int j = 0; j < bucketArr.get(i).size(); j++) {
            arr[index++] = bucketArr.get(i).get(j);
        }
    }
}

要点

  • 桶排序的时间复杂度是

   O(N + C)
= O(N) + O(M ∗ (N/M ∗ log(N/M)))
= O(N ∗ (log(N/M) + 1))

  • 由于 log(N/M) 通常很小,所以有时可以直接认为是 O(N)
  • 桶数量M越多,时间效率越高,然而桶数量M越多占用空间也就越大
  • 既可以升序排序,也可以降序排序,把最后的数组反向遍历即可

适用场景

  • 桶排序一般不常用
⚠️ **GitHub.com Fallback** ⚠️