排序算法9-桶排序

桶排序

• 平均时间复杂度:O(n+k)
• 最好情况:O(n+k)
• 最坏情况:O(n^2)
• 空间复杂度:O(n+k)
• 排序方式:Out-place
• 稳定性:稳定

算法步骤:
1.按照待排序序列的最大最小值来创建桶
2.依次将数字分配到不同的桶中
3.对每个桶做排序操作
4.依次取出桶里的值

桶排序在某种意义上和前面的计数排序很像，但是计数排序只能使用于整数排序，而桶排序可以用于小数。

function insertionSort(arr) {
  let len = arr.length;
  let temp;
  for (let i = 1; i < len; i++) {
    let j = i;
    while (j > 0 && arr[j] < arr[j - 1]) {
      temp = arr[j];
      arr[j] = arr[j - 1];
      arr[j - 1] = temp;
      j--;
    }
  }
}

function bucketSort(arr) {
  // 最大最小值不循环了，简单通过api获取
  let minValue = Math.min(...arr);
  let maxValue = Math.max(...arr);

  let bucketSize = 10;
  let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  let buckets = Array(bucketCount)
    .fill(1)
    .map(() => []);

  for (let i = 0; i < arr.length; i++) {
    buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
  }

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

  return arr;
}