桶排序

问题

实现桶排序算法，理解其工作原理和适用场景。

解答

桶排序是一种分布式排序算法，将元素分散到多个桶中，每个桶单独排序后再合并。

基本实现

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

  // 找出最大值和最小值
  let min = arr[0];
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < min) {
      min = arr[i];
    } else if (arr[i] > max) {
      max = arr[i];
    }
  }

  // 计算桶的数量
  const bucketCount = Math.floor((max - min) / bucketSize) + 1;
  
  // 创建桶
  const buckets = new Array(bucketCount);
  for (let i = 0; i < bucketCount; i++) {
    buckets[i] = [];
  }

  // 将元素分配到桶中
  for (let i = 0; i < arr.length; i++) {
    const bucketIndex = Math.floor((arr[i] - min) / bucketSize);
    buckets[bucketIndex].push(arr[i]);
  }

  // 对每个桶内部排序，然后合并
  const result = [];
  for (let i = 0; i < buckets.length; i++) {
    // 桶内使用插入排序（小数据量时效率高）
    insertionSort(buckets[i]);
    result.push(...buckets[i]);
  }

  return result;
}

// 插入排序（用于桶内排序）
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const current = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

// 测试
const arr = [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51];
console.log(bucketSort(arr, 0.1)); 
// [0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]

针对 0-1 范围浮点数的优化版本

function bucketSortFloat(arr, bucketCount = 10) {
  if (arr.length === 0) return arr;

  // 创建桶
  const buckets = Array.from({ length: bucketCount }, () => []);

  // 分配元素到桶（假设元素在 [0, 1) 范围内）
  for (const num of arr) {
    const index = Math.floor(num * bucketCount);
    // 处理边界情况：num === 1 时放入最后一个桶
    const bucketIndex = index === bucketCount ? bucketCount - 1 : index;
    buckets[bucketIndex].push(num);
  }

  // 桶内排序并合并
  return buckets.flatMap(bucket => bucket.sort((a, b) => a - b));
}

// 测试
const floats = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68];
console.log(bucketSortFloat(floats));
// [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

图解过程

原始数组: [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]

分桶（桶大小 0.1）:
桶[2]: [0.23, 0.25]
桶[3]: [0.32]
桶[4]: [0.42, 0.47]
桶[5]: [0.52, 0.51]

桶内排序:
桶[2]: [0.23, 0.25]
桶[3]: [0.32]
桶[4]: [0.42, 0.47]
桶[5]: [0.51, 0.52]

合并: [0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]

关键点

• 时间复杂度：平均 O(n + k)，最坏 O(n²)，k 为桶的数量
• 空间复杂度：O(n + k)，需要额外空间存储桶
• 适用场景：数据分布均匀、范围已知的情况，如 0-1 之间的浮点数
• 桶大小选择：桶太少导致桶内元素多，桶太多浪费空间，通常取 n 或 √n
• 非比较排序：通过分布而非比较来排序，可突破 O(n log n) 的下界