1. 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

一 桶排序思路

先扫描一遍序列求出最大值 maxV 和最小值 minV ，设桶的个数为 k ，则把区间 [minV, maxV] 均匀划分成 k 个区间，每个区间就是一个桶。将序列中的元素分配到各自的桶。然后对每个桶内的元素进行排序，可以选择任意一种排序算法。最后将各个桶中的元素合并成一个大的有序序列。
假设数据是均匀分布的，则每个桶的元素平均个数为 n/k， 。假设选择用快速排序对每个桶内的元素进行排序，那么每个桶排序的时间复杂度为 O((n/k)log(n/k)) ，总的时间复杂度为：
O(n)+O(k)O((n/k)log(n/k)) = O(n+nlog(n/k)) = O(n+nlogn-nlogk )。
当 k 接近于 n 时，桶排序的时间复杂度就可以近似认为是 O(n) 的。即桶越多，时间效率就越高，而桶越多，空间就越大。

二 实现

  1. package com.sort.s09bucketsort;
  3. import com.sort.s06quicksort.QuickSort;
  4. import org.junit.Test;
  6. import java.util.Arrays;
  8. public class BucketSort {
  10.     private int default_bucketSize = 1;
  12.     public int[] sort(int[] array,int bucketSize){
  13.         if(null == array || array.length<2){
  14.             return array;
  15.         }
  16.         bucketSize = bucketSize<default_bucketSize?default_bucketSize:bucketSize;
  17.         int[] arrayToSot = Arrays.copyOf(array,array.length);
  18.         return bucketSort(arrayToSot,bucketSize);
  19.     }
  22.     private int[] bucketSort(int[] arr,int bucketSize){
  23.         /** 找到最大值和最小值 */
  24.         int minValue = arr[0];
  25.         int maxValue = arr[0];
  26.         for (int value : arr) {
  27.             minValue = value<minValue?value:minValue;
  28.             maxValue = value>maxValue?value:maxValue;
  29.         }
  30.         /** 计算桶的数量，并对桶进行初始化 */
  31.         int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
  32.         int[][] buckets = new int[bucketCount][0];
  34.         /** 利用映射函数将数据分配到各个桶中 */
  35.         for (int i = 0; i < arr.length; i++) {
  36.             // 计算落在哪一个桶里面
  37.             int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
  38.             buckets[index] = arrAppend(buckets[index], arr[i]);
  39.         }
  41.         /** 对桶内数据进行排序  随意各种排序方式
  42.          *  这里便使用快速排序
  43.          * */
  44.         int arrIndex = 0;// 排序游标
  45.         for(int[] bucket :buckets){
  46.             QuickSort quickSort = new QuickSort();
  47.             int[] sortBucket = quickSort.quickSort(bucket);
  48.             for(int value : sortBucket){
  49.                 arr[arrIndex++] = value;
  50.             }
  51.         }
  52.         return arr;
  53.     }
  55.     /**
  56.      * 自动扩容，并保存数据
  57.      * @param arr
  58.      * @param value
  59.      */
  60.     private int[] arrAppend(int[] arr, int value) {
  61.         arr = Arrays.copyOf(arr, arr.length + 1);
  62.         arr[arr.length - 1] = value;
  63.         return arr;
  64.     }
  66.     public void println(int [] a) {
  67.         for(int x:a) {
  68.             System.out.print(" "+x);
  69.         }
  70.         System.out.println("");
  71.     }
  73.     //  1 2 3 4 4 5 6 7 8 10 12 22 30 31 34 43 50 55 100
  74.     @Test
  75.     public void testBucketSort(){
  76.         int[] nums = {5, 3, 4, 6, 7, 1, 2, 8, 4, 10, 100, 50, 30, 22, 34, 55, 43, 12, 31};
  77.         BucketSort sort = new BucketSort();
  78.         sort.println(sort.sort(nums,4));
  79.     }
  80. }