如何对唯一、有界数组进行最有效的排序？

Question

我认为这是一个重复问题，但我找不到。

假设我们有一个数组，我们知道每个值都是唯一的，且每个值都在一个范围内。例如，假设我们知道该数组由介于0和100之间的唯一值组成。示例：

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

我想将这个数组按照以下方式排序：

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

显然，我可以使用快速排序或任何其他比较排序，但其时间复杂度为O(n log n)。也存在非比较排序，例如基数排序、桶排序、计数排序等，但据我所知，这些排序都不能维护值必须是唯一的约束条件。

通常情况下，允许的约束条件越多，算法就可以变得越有效率。是否存在任何更有效率的算法来处理唯一有界数组？如果没有，那么哪种非比较排序算法对于这类型数据集来说最有效率？

- Ryan Peschel

---

我不知道用什么算法来排序键，但是 Object.keys( arr.reduce( (o,v) => { o[ v ] = null; return o; }, {} ) ) 可以尝试一下。 - Kaiido

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);

- Patrick Roberts

---

啊，我明白了。很不幸，由于我的列表并不是很大（刚刚进行了基准测试），所以这仍然比插入排序慢，但我想它在时间复杂度上确实更好。如果没有更快的方法出现，我想我会继续使用插入排序，并接受这个答案，因为它从技术上讲是对我的问题的回答。 - Ryan Peschel

@RyanPeschel 是的，插入排序对于小列表来说往往非常快。渐进时间复杂度是无关紧要的，除非n的值非常大（即> 1000000）。 - Patrick Roberts

是的，我在发布后搜索了一下才意识到这一点。如果有人碰巧有一个大列表，那么这个答案对他们可能会有所帮助。 - Ryan Peschel

这不是计数排序的变体吗？ - rcgldr

Answer 2

这样的东西？

const arr1 = [ 5, 46, 15, 83, 55, 28  ]

const  min = Math.min( ...arr1)

const res = []
for(let v of arr1) res[v-min] = v
for(let i=res.length;i--;) if (res[i]===undefined) res.splice(i, 1)

console.log( res )

.as-console-wrapper { max-height: 100% !important; top: 0; }

- Mister Jojo

Answer 3

我建议使用计数排序，但是使用字节数组来存储通常用于计数的值，因为由于要排序的数组具有唯一值，计数值只会是0或1。这也适用于数组中没有任何值出现超过255次的情况（这样每个计数仍将适合于无符号字节）。

- rcgldr