javascript - 对唯一的有界数组进行排序的最有效方法？

Question

我认为这是重复的，但我找不到。
假设我们有一个数组，我们知道每个值都是唯一的，并且每个值都在一个范围之间。例如，假设我们知道数组由 0 到 100 之间的唯一值组成。示例:

[ 5, 46, 15, 83, 55, 28 ]

然后我想将此数组排序为以下内容:

[ 5, 15, 28, 46, 55, 83 ]

显然我可以使用 Quicksort 或任何其他比较排序，但那将是 O(n log n) .也存在非比较排序，例如基数排序、桶排序、计数排序等，但据我所知，这些排序都没有保持值必须唯一的约束。
通常情况下，您允许的约束越多，您的算法就越有效。是否有任何算法对唯一的有界数组更有效？如果不是，哪种非比较排序算法对这种类型的数据集最有效？

Answer 1

给定唯一值和受限范围的约束，您可以声明一个数组，其长度足以容纳给定范围内的每个唯一整数，然后您可以执行特殊情况的桶排序，其中每个桶总是能够包含唯一的值，最后过滤数组以删除剩余的空槽。与其他非比较排序算法一样，这种方法是 O(n) 渐近时间复杂度。

const input = [5, 46, 15, 83, 55, 28];

function sort(unsorted, lower, upper) {
  const sorted = Array(upper - lower);

  for (let i = 0; i < unsorted.length; ++i) {
    sorted[unsorted[i] - lower] = unsorted[i];
  }

  return sorted.filter(() => true);
}

const output = sort(input, 0, 100);

console.log(output);