Какой алгоритм работы элементов массива наиболее эффективен?

Question

Я решаю проблемы с UVa-сайтом, у меня проблема в том, что я должен отсортировать целые числа настолько быстро, насколько возможно .

Я пробовал сортировку по пузырькам, но она неэффективна. Я пробовал быструю сортировку, которая использует рекурсию, но в результате получается StackOverflowException, так как ввод очень большой ( почти 20 миллионов ).

Ограничение по времени задачи составляет всего 5 секунд . У кого-нибудь есть идеи о том, как реализовать это более эффективно?

Answer 1

Я поддержу предложение, которое вы рассматриваете как несопоставимые виды.Вы говорите, что сортируете целые числа ... какой диапазон целых чисел, в частности, значения могут попадать внутрь?Считать / сортировать ведра было бы глупо быстро.

Answer 2

Я решил проблему с помощью C и функции qsort () , попробуйте.

Answer 3

Вам не обязательно писать рекурсивную сортировку quicksort.

Вы можете взять рекурсивный алгоритм и переписать его для использования стека, избегая рекурсии.

Пример реализации этого:

• Пятничные алгоритмы: итеративная быстрая сортировка
• Викиучебники: реализация алгоритма / сортировка / быстрая сортировка
• CodeProject: Итеративная быстрая сортировка

Answer 4

Поскольку вы сортируете только целые числа, radix sort может быть хорошей идеей. Приятной особенностью этого алгоритма является то, что он всегда занимает одинаковое количество времени, которое зависит от количества элементов для сортировки, а не от того, насколько они «не отсортированы».

См. Также Дональда Кнута Искусство компьютерного программирования том 3, Сортировка и поиск . Алгоритм описан в разделе 5.2.5. Сортировка по распределению , начиная со страницы 168. Псевдокод алгоритма: Алгоритм R на странице 172 (номера страниц из второго издания).

Мало того, что алгоритм достаточно эффективен, я также думаю, что его легко понять и реализовать (ну, по крайней мере, для алгоритма сортировки).

Answer 5

Быстрая сортировка может быть записана на месте .Поскольку он не требует (ну, не очень) дополнительной памяти, я не думаю, что это вызовет ошибку, если вы используете эту версию.Если у вас все еще есть такая ошибка, вы можете рассмотреть возможность рандомизации ввода.

Кроме того, вы можете рассмотреть несопоставимую сортировку, такую ​​как подсчет сортировки .Этот вид алгоритмов сортировки имеет свои ограничения, но обычно требует меньше времени, например, O (n).

Answer 6

Используйте Timsort: http://en.wikipedia.org/wiki/Timsort

Что не может решить ваш StackOverflow.Вы можете реализовать их итеративно, используя стек.