桶排序

实现

• 使用Math.min()、Math.max()和展开运算符(...)来找到给定数组的最小值和最大值。
• 使用Array.from()和Math.floor()来创建适当数量的buckets（空数组）。
• 使用Array.prototype.forEach()将每个桶填充为来自数组的适当元素。
• 使用Array.prototype.reduce()、展开运算符(...)和Array.prototype.sort()来对每个桶进行排序并将其附加到结果中。

const bucketSort = (arr, size = 5) => {
  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const buckets = Array.from(
    { length: Math.floor((max - min) / size) + 1 },
    () => []
  );
  arr.forEach(val => {
    buckets[Math.floor((val - min) / size)].push(val);
  });
  return buckets.reduce((acc, b) => [...acc, ...b.sort((a, b) => a - b)], []);
};

bucketSort([6, 3, 4, 1]); // [1, 3, 4, 6]

复杂度

该算法的平均时间复杂度为O(n + k)，其中n是输入数组的大小，k是桶的数量。