09桶排序

桶排序 (箱排序)的原理是将待排序序列分到有限数量的桶里面，然后对每个桶再分别排序（可以使用其它的排序算法或者是递归使用桶排序算法），最后将各个桶中的数据有序的合并起来成为一个整体有序的序列。排序过程：1.假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶2.将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序3.将各个桶中的数据有序的合并起来
实例分析
设有数组 array = [29, 25, 3, 49, 9, 37, 21, 43]，那么数组中最大数为 49，先设置 5 个桶，那么每个桶可存放数的范围为：09、1019、2029、3039、40~49，然后分别将这些数放人自己所属的桶，如下图：

然后，分别对每个桶里面的数进行排序，或者在将数放入桶的同时用插入排序进行排序。最后，将各个桶中的数据有序的合并起来，如下图：

/**
 * 
 * @param {*} arr 待排序数组
 * @param {*} bucketCount 桶的个数
 */
function bucketSort(arr, bucketCount) {
    console.log('排序前：'+arr);
    if (arr.length <= 1) {
      return arr; //长度小于等于1不用排序
    }
    var buckets, //装桶的桶，下标控制桶的编号
        result = [],
        minValue = arr[0],
        maxValue = arr[0];
   
    //获取数组中的最大值和最小值
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];  // 输入数据的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i]; // 输入数据的最大值
      }
    }

    //桶的初始化
    bucketCount = parseInt(bucketCount) > 0 ? parseInt(bucketCount) : 10; //默认桶的个数为10
    var bucketRange = (maxValue - minValue) / bucketCount; //每个桶的范围
    buckets = new Array(bucketCount);
    for (let i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }

    //利用映射函数将数据分配到各个桶中
    for (let i = 0; i < arr.length; i++) {
        let index = Math.floor((arr[i] - minValue) / bucketRange);
        if(buckets[index]){
            buckets[index].push(arr[i]);
        }else{
            buckets[index] = []; //没有值则生成新的桶，并把值放到对应桶中
            buckets[index][0] = arr[i];
        }
    }

    // 对每个桶进行排序，这里使用了插入排序
    for (let i = 0; i < buckets.length; i++) {
        insertSort(buckets[i]);
    }
    console.log('插入各个桶之后的情况：');
    console.log(buckets);
    console.log('========================');

    //合并桶输出结果
    for (let j = 0; j < buckets.length; j++) {
        result = result.concat(buckets[j]);
    }

    console.log('排序结果：'+result);
    return arr;
}

function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) { // 从第2个元素开始插入
      let temp = arr[i];　// 待插入元素
      j = i - 1;
      while (j >= 0 && temp < arr[j]) { // 从后向前，找到比其小的数的位置
          arr[j + 1] = arr[j]; // 向后移动
          j--;
      }
      arr[j + 1] = temp;
    }
    return arr;
}

var arr = [9,3,4,0,2,8,5,1,7,6,11,10,18,15,17,12,16,13,19,14];
bucketSort(arr, 10);

/**
排序前：9,3,4,0,2,8,5,1,7,6,11,10,18,15,17,12,16,13,19,14
插入各个桶之后的情况：
[ [ 0, 1 ],
  [ 2, 3 ],
  [ 4, 5 ],
  [ 6, 7 ],
  [ 8, 9 ],
  [ 10, 11 ],
  [ 12, 13 ],
  [ 14, 15 ],
  [ 16, 17 ],
  [ 18 ],
  [ 19 ] ]
========================
排序结果：0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19
*/