Какой самый быстрый способ сортировки 1 миллиона целых чисел, если целые числа находятся в диапазоне [1100]?

Question

Примечания: я думал о сортировке по Radix, сортировке по сегментам, сортировке по счетам.

Есть ли в любом случае, чтобы достичь больших O (n)?

Answer 1

Вы можете использовать подсчет сортировки .

Подсчет сортировки (иногда называемый ультра сортировкой или математической сортировкой) - это алгоритм сортировки, который (подобно сортировке по сегментам) использует знание диапазона чисел в массиве, который нужно отсортировать (массив A).

Счетная сортировка является стабильной сортировкой и имеет время выполнения Θ (n + k), где n и k - длины массивов A (входной массив) и C (счетный массив) соответственно. Чтобы этот алгоритм был эффективным, k не должно быть намного больше, чем n.

В этом случае k равно 100, а n равно 1000000.

Answer 2

Счетная сортировка была бы очевидным выбором при этих обстоятельствах.Да, при правильной реализации он должен иметь линейную сложность.

Answer 3

как насчет того, чтобы просто посчитать вхождение каждого целого числа и затем распечатать их все. звучит как O (n)

Answer 4

Полагаю, вы имеете в виду, что хотите добиться небольшого O (n); тогда сортировка ведра будет самой быстрой. Фактически, поскольку вы знаете диапазон целых чисел, то использование сортировки по сегментам просто становится проблемой подсчета вхождений чисел, которые можно выполнить за O (n), то есть за линейное время.

Так называемая счетная сортировка - это просто особый случай сортировки по сегментам.

Answer 5

С учетом сортировки вы получаете O (N), если диапазон фиксирован и мал (как 1..100:))

Answer 6

Использование Radix Sort (в рубине):

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

Answer 7

Вот подсчет в 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 (" ")) 

Answer 8

Для тех, кто заинтересован, я быстро собрал этот кусочек 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. (Единственное, что вам нужно знать, это то, что комбинатор K пишется tap в Ruby.)

И это действительно чертовски быстро, хотя, к сожалению, я не смог превзойти встроенную оптимизированную вручную O (n & thinsp; log & thinsp; n) сортировку, написанную на C в MRI и YARV и Java в JRuby.