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

Ответ 1

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

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

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

Ответ 6

Для всех, кого это интересует, я быстро собрал этот кусок 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 :-)

Я даже не знал, что у него есть имя. Он должен передать идею даже тому, кто никогда раньше не видел Руби. (Единственное, что вам нужно знать, это то, что комбинатор K пишется tap в Ruby.)

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

Ответ 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 (" ")) 

Ответ 8

Использование Radix Sort (In 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