九、桶排序

永久链接： https://tech.souyunku.com/?p=9381

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

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

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

1. 什么时候最快

当输入的数据可以均匀的分配到每一个桶中。

2. 什么时候最慢

当输入的数据被分配到了同一个桶中。

3. JavaScript 代码实现

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }

    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                // 输入数据的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                // 输入数据的最大值
      }
    }

    //桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;   
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }

    //利用映射函数将数据分配到各个桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }

    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      // 对每个桶进行排序，这里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                      
        }
    }

    return arr;
}

4. Java 代码实现

/** 
 * 桶排序假设输入元素均匀而独立的分布在区间[0，1）上； 
 * 桶排序的核心思想是，将[0，1）分为n个大小相同的子区间， 
 * 上一个区间里的元素都比下一个区间里的元素小，然后对 
 * 所有区间里的元素排序，最后顺序输出所有区间里的元素， 
 * 达到对所有元素排序的目的。 
 * @author yuncong 
 * 
 */  
public class bucketSort {  
    public void sort(Double[] a) {  
        int n = a.length;  

        /** 
         * 创建链表（桶）集合并初始化，集合中的链表用于存放相应的元素 
         */  
        int bucketNum = 10; // 桶数  
        LinkedList<LinkedList<Double>> buckets = new LinkedList<LinkedList<Double>>();  
        for(int i = 0; i < bucketNum; i++){  
            LinkedList<Double> bucket = new LinkedList<Double>();  
            buckets.add(bucket);  
        }  
        // 把元素放进相应的桶中  
        for(int i = 0; i < n; i++){  
            int index = (int) (a[i] * bucketNum);  
            buckets.get(index).add(a[i]);  
        }  
        // 对每个桶中的元素排序，并放进a中  
        int index = 0;  
        for (LinkedList<Double> linkedList : buckets) {  
            int size = linkedList.size();  
            if (size == 0) {  
                continue;  
            }  
            /** 
             * 把LinkedList<Double>转化为Double[]的原因是，之前已经实现了 
             * 对数组进行排序的算法 
             */  
            Double[] temp = new Double[size];  
            for (int i = 0; i < temp.length; i++) {  
                temp[i] = linkedList.get(i);  
            }  
            // 利用插入排序对temp排序  
            new InsertSort().sort(temp);  
            for (int i = 0; i < temp.length; i++) {  
                a[index] = temp[i];  
                index++;  
            }  
        }  

    }  

    public static void main(String[] args) {  
        Double[] a = new Double[]{0.3, 0.6, 0.5};  
        new BucketSort().sort(a);  
        for (int i = 0; i < a.length; i++) {  
            System.out.println(a[i]);  
        }  
    }