根据待排序数据元素的数量，选定一定数量的桶将元素均匀分布到各个桶中，对每个桶进行桶内排序(稳定或不稳定取决于具体问题)
    排好后再依次将桶中元素取出

    时间复杂度 O(n + m)其中n为输入规模，m为桶的个数

    为了使桶排序更加高效，我们需要做到这两点：

    1. 在额外空间充足的情况下，尽量增大桶的数量
    2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

    桶排序.png

    1. import java.util.*;
    3. public class Main {
    4.     static final int SIZE = 100000; //每个桶的范围大小
    5.     public static void main(String[] args) {
    6.         Scanner sc = new Scanner(System.in);
    8.         int n = sc.nextInt();
    9.         int[] a = new int[n];
    11.         for (int i = 0; i < n; i++)
    12.             a[i] = sc.nextInt();
    14.         //找最大最小值
    15.         int max = a[0], min = a[0];
    16.         for (int i = 1; i < a.length; i++) {
    17.             max = Math.max(a[i], max);
    18.             min = Math.min(a[i], min);
    19.         }
    20.         //确定桶的个数
    21.         int bs = (max - min) / SIZE + 1;
    22.         List<Integer>[] b = new ArrayList[bs];
    23.         for (int i = 0; i < bs; i++)
    24.             b[i] = new ArrayList<>();
    25.         for (int i = 0; i < a.length; i++) {
    26.             int idx = (a[i] - min) / SIZE;
    27.             b[idx].add(a[i]);
    28.         }
    30.         int idx = 0;
    31.         for (int i = 0; i < bs; i++) {
    32.             if (!b[i].isEmpty()) {
    33.                 Collections.sort(b[i]);    //这里也可以自己实现桶内排序
    34.                 for (int x : b[i])
    35.                     a[idx++] = x;
    36.             }
    37.         }
    39.         for (int i = 0; i < n; i++) {
    40.             System.out.print(a[i] + " ");
    41.         }
    42.     }
    43. }