Что самый быстрый путь состоит в том, чтобы отсортировать 1 миллион целых чисел, когда целые числа от диапазона [1,100]?
Примечания: Я думал о виде Основания, блочной сортировке, считая вид.
Там должен так или иначе достигнуть большого O (n)?
6 ответов
Вы можете использовать счетную сортировку.
Счетная сортировка (иногда называемая ultra sort или math sort) - это алгоритм сортировки, который (как и bucket sort) использует преимущество знания диапазона чисел в сортируемом массиве (массив A).
Counting sort является устойчивой сортировкой и имеет время работы Θ(n+k), где n и k - длины массивов A (входной массив) и C (счетный массив), соответственно. Для того чтобы этот алгоритм был эффективным, k не должно быть намного больше n.
В данном случае k равно 100, а n равно 1000000.
Счетная сортировка была бы очевидным выбором в этих обстоятельствах. Да, правильно реализованный, он должен иметь линейную сложность.
как насчет того, чтобы просто подсчитать появление каждого целого числа и затем вывести их все. звучит как O(n)
Я полагаю, вы имеете в виду, что хотите достичь небольшого O(n); тогда bucket sort будет самым быстрым. На самом деле, поскольку вы знаете диапазон целых чисел, то использование сортировки по ведрам становится просто проблемой подсчета встречающихся чисел, что может быть сделано за O(n), т.е. за линейное время.
Так называемая счетная сортировка - это просто частный случай ведерной сортировки.
При сортировке с подсчетом вы получите O (N), если диапазон фиксирован и мал (например, 1..100 :))
Для тех, кому интересно, я быстро набросал этот кусок 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 log n), которая написана на C в MRI и YARV и Java в JRuby.