带你读《图解算法小抄》十四、排序（18）

带你读《图解算法小抄》十四、排序（17）https://developer.aliyun.com/article/1348133?groupCode=tech_library

3）完整代码：

function bucketSort(arr, bucketSize = 5) {
  if (arr.length === 0) {
    return arr;
  }
  const minValue = Math.min(...arr);
  const maxValue = Math.max(...arr);
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  const buckets = new Array(bucketCount);
  for (let i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }
  for (let i = 0; i < arr.length; i++) {
    const bucketIndex = Math.floor((arr[i] - minValue) / bucketSize);
    buckets[bucketIndex].push(arr[i]);
  }
  const sortedArray = [];
  for (let i = 0; i < buckets.length; i++) {
    if (buckets[i]) {
      insertionSort(buckets[i]);
      sortedArray.push(...buckets[i]);
    }
  }
  return sortedArray;
}

 在这个示例中，我们使用bucketSort函数实现桶排序。我们首先确定桶的数量，根据元素范围和分布计算出合适的桶的数量。然后，我们创建桶数组，并将待排序元素根据值分配到相应的桶中。接下来，对每个非空的桶进行排序，我们可以使用插入排序等算法。最后，将每个桶中的元素按照顺序合并，得到最终的排序结果。

4）复杂度

桶排序的计算复杂度取决于用于对每个桶进行排序的算法、要使用的桶的数量以及输入是否均匀分布。

当桶内使用的排序算法是插入排序时，桶排序的最坏情况时间复杂度为 O(n^2)。这是最常见的情况，因为预期是每个桶的元素数量相对于整个列表不会太多。在最坏情况下，所有元素都被放入一个桶中，导致运行时间降低到插入排序的最坏情况复杂度（所有元素按逆序排列）。如果所使用的中间排序算法的最坏情况运行时间是 O(n * log(n))，那么桶排序的最坏情况运行时间也将是 O(n * log(n))。

在平均情况下，当元素在桶之间的分布相对均匀时，可以证明桶排序的平均运行时间为 O(n + k)，其中 k 是桶的数量。

5）参考资料

维基百科上的桶排序

8.基数排序

在计算机科学中，基数排序（Radix Sort）是一种非比较的整数排序算法，它通过将具有相同有效位置和值的数字按位进行分组来排序具有整数键的数据。这需要使用位数制表示法，但由于整数可以表示字符串（例如，名称或日期）和特定格式的浮点数，因此基数排序不仅限于整数。

名称的由来

在数学的数字系统中，基数或底数是用于表示位置制数字系统中的数字的唯一数字的数量，包括数字零。例如，二进制系统（使用数字0和1）的基数为2，十进制系统（使用数字0到9）的基数为10。

带你读《图解算法小抄》十四、排序（19）https://developer.aliyun.com/article/1348131?groupCode=tech_library