当整数范围为[1,100]时，对100万个整数进行排序的最快方法是什么？

Question

备注：我考虑过基数排序、桶排序和计数排序。

有没有什么方法可以达到O(n)？

- wiznaibus

---

通常情况下，即使列表中的每个数字都小于100，也无法以O(n)的时间复杂度对列表进行排序。 - SLaks

@SLaks说的“O(N lgN)的最小值只适用于基于比较的排序算法。” - Jerry Coffin

在这种情况下，你可以通过简单地数一数1到100之间的元素来实现。 - Alexandre C.

我认为基数排序可以实现O(n)。 - Rambo

Answer 1

你可以使用计数排序。

计数排序（有时也称为超级排序或数学排序）是一种排序算法，它（像桶排序一样）利用了知道要排序的数组A中数字的范围的优势。

计数排序是一种稳定的排序算法，其运行时间为Θ（n+k），其中n和k分别是数组A（输入数组）和C（计数数组）的长度。为了使此算法有效，k必须不比n大得多。

在这种情况下，k为100，n为1000000。

- Mark Byers

Answer 2

在这种情况下，计数排序将是显而易见的选择。是的，如果正确实现，它应该具有线性复杂度。

- Jerry Coffin

Answer 3

只需计算每个整数的出现次数，然后打印它们。听起来像是O(n)的时间复杂度。

- second

---

是的，这正是计数排序。这表明大多数算法并不难；你自己也能想出来。 :-) - ShreevatsaR

计数排序比这个稍微复杂一些（它可以对键进行排序，但可以处理关联的数据），但是基本思想是正确的。 - Karoly Horvath

Answer 4

我假设你想要实现一个小O（n）的算法，那么桶排序是最快的。事实上，由于你知道整数的范围，因此使用桶排序只需计算数字出现的次数即可，在O(n)的时间内完成。

所谓的计数排序其实就是桶排序的一种特殊情况。

- Lie Ryan

---

不，计数排序并不是桶排序的特例。在桶排序中，您实际上将元素存储在桶中。而在计数排序中，您只存储计数。 - Karoly Horvath

Answer 5

如果范围是固定且较小的（例如1..100），使用计数排序可以获得O(N)的时间复杂度。

- Razvi

Answer 6

这是Scala中的计数排序：

val res = Array.fill (100)(0)
val r = util.Random 
// generate data to sort
val nums = for (i <- 1 to 1000*1000) yield r.nextInt (100)
for (i <- nums) res(i) += 1
println (res.mkString (" ")) 

- user unknown

Answer 7

对于任何感兴趣的人，我在阅读答案之前很快地编写了这个 Ruby 片段：

module Enumerable
  def counting_sort(k)
    reduce(Array.new(k+1, 0)) {|counting, n| counting.tap { counting[n] += 1 }}.
    map.with_index {|count, n| [n] * count }.flatten
  end
end

ary = Array.new(1_000_000){ rand(100) + 1 }
ary.counting_sort(100) # I'll spare you the output :-)

我甚至不知道它有一个名字。它应该能够传达这个想法，即使对于从未见过Ruby的人来说也是如此。（你唯一需要知道的是在Ruby中，K组合器被拼写为tap）

而且它确实非常快，尽管不幸的是，我无法打败内置的手动优化的O(n log n)排序，在MRI、YARV和JRuby中都是用C编写的。

- Jörg W Mittag

Answer 8

使用基数排序（在Ruby中）：

def sort(array)
sorted_array = Array.new(100,[])
array.each do |t|
sorted_array[t-1] = sorted_array[t-1] + [t]
end
sorted_array.flatten!
end

- user3433919