如果要对大量的一定范围内的数据进行排序，比如100000个0-99的数字进行排序，可以使用桶排序。
    在设置了桶个数对应数字范围的情况下，时间复杂度O(N)
    代码：

    1.   public List<Integer> sort(List<Integer> A) {
    2.     int k = 100;
    3.     ArrayList<LinkedList<Integer>> buckets = new ArrayList<>();
    4.     ArrayList<Integer> list = new ArrayList<>();
    6.     for (int i = 0; i < k; i++) {
    7.       buckets.add(new LinkedList<>());
    8.     }
    9.     for (int item : A) {
    10.       buckets.get(item % k).add(item);
    11.     }
    12.     for (LinkedList<Integer> bucket : buckets) {
    13.       list.addAll(bucket);
    14.     }
    15.     return list;
    16.   }

    测试代码

    1.   @Test
    2.   public void testBucketSort() {
    3.     List<Integer> A = gen(100000);
    4.     long startTime = System.currentTimeMillis();
    5.     BucketSort bucketSort = new BucketSort();
    6.     A = bucketSort.sort(A);
    7.     assertSorted(A);
    8.     System.out.println("Time: " + (System.currentTimeMillis() - startTime));
    9.   }
    12.   private List<Integer> gen(int n) {
    13.     List<Integer> list = new ArrayList<>(n);
    14.     for (int i = 0; i < n; i++) {
    15.       list.add((int) (Math.random() * 100));
    16.     }
    17.     return list;
    18.   }
    20.   private void assertSorted(List<Integer> A) {
    21.     Integer o = Integer.MIN_VALUE;
    22.     for (int i : A) {
    23.       if (o > i) {
    24.         Assert.fail("Array not in sorted order");
    25.       }
    26.       o = i;
    27.     }
    28.   }

    结果

    1. Time: 27
    3. Process finished with exit code 0

    使用归并排序时间=108
    使用选择排序时间=1967

    更通用的代码
    多一个步骤：对桶内元素进行排序

    1.   public List<Integer> sort(List<Integer> A, int k, int max, int min) {
    2.     ArrayList<LinkedList<Integer>> buckets = new ArrayList<>();
    3.     ArrayList<Integer> ret = new ArrayList<>();
    4.     // min 到 max 之间的长度
    5.     int D = max - min + 1;
    6.     QuickSort quicksort = new QuickSort();
    7.     // 初始化所有的桶
    8.     for (int i = 0; i < k; i++) {
    9.       buckets.add(new LinkedList<>());
    10.     }
    11.     // 把元素放到桶里
    12.     for (int item : A) {
    13.       // 计算的是 item 对应的是哪个桶
    14.       int key = (item - min) * k / D;
    15.       buckets.get(key).add(item);
    16.     }
    17.     // 将桶里的值排序后放回到结果集中
    18.     for (int i = 0; i < k; i++) {
    19.       ret.addAll(quicksort.sortList(buckets.get(i)));
    20.     }
    21.     return ret;
    22.   }