桶排序

[louzhedong]

算法名称

桶排序

实现思路

• 大致思路是将数组分到有限个桶中
• 每个桶中存储一定范围之内的数
• 通过映射函数，将待排序数组中的元素映射到各个对应的桶中
• 最后将所有桶中的数据按顺序连接起来
• 本质上是一种已空间换时间的方式

算法分析

对每个数据进行函数映射，确定放到哪个桶中的时间复杂度为O(N)

对每个桶进行排序的时间复杂度跟进桶内排序算法而定

当每个桶只有一个数据时，效率最高，为O(N)

算法实现

function BucketSort(array) {
  var min = Number.MAX_VALUE;
  var max = Number.MIN_VALUE;
  var length = array.length;
  var bucketNum;

  // 获取数组最大值和最小值
  for (var i = 0; i < length; i++) {
    if (array[i] < min) {
      min = array[i];
    }
    if (array[i] > max) {
      max = array[i];
    }
  }

  // 计算桶的数量
  bucketNum = Math.ceil((max - min) / length) + 1;

  var bucketArray = [];
  for (var i = 0; i < bucketNum; i++) {
    bucketArray[i] = [];
  }

  for (var j = 0; j < length; j++) {
    var cursor = Math.floor((array[j] - min) / length);
    innerSort(bucketArray[cursor], array[j]);
  }

  var newArray = [];
  for (var i = 0; i < bucketNum; i++) {
    for (var j = 0; j < bucketArray[i].length; j++) {
      newArray.push(bucketArray[i][j]);
    }
  }

  return newArray;

}


// 内部排序
function innerSort(array, current) {
  var length = array.length;
  if (length === 0) {
    array[0] = current;
    return;
  }
  for (var i = length - 1; i >= 0; i--) {
    if (array[i] > current) {
      array[i + 1] = array[i];
    } else {
      array[i + 1] = current;
      break;
    }
  }
}