У меня есть вопрос о быстрой сортировке и выборе сортировки. Я прочитал много сообщений здесь, но ни один из них не отвечает на мой вопрос. Посмотрите: У нас есть 10 ГБ номеров, и мы должны их отсортировать. Тем не менее, у нас имеется только 800 Мб памяти, поэтому слияние не может быть и речи. Теперь, из-за огромного размера массива, вопрос о пузырях тоже не может быть и речи. Лично я считаю, что оба алгоритма sortin отлично подходят для этой работы, однако я должен выбрать только один из них - тот, который работает лучше. Quicksort: Обычно имеет: O (N * logN) и наихудший: O (N^2) Selectionsort: обычно & худшее: O (N^2) Быстрое сортирование кажется лучше, но по моему опыту, я думаю, что Selectionsort немного лучше, чем быстрая сортировка для огромных структур данных. Как вы думаете? Спасибо!Quicksort или Selectionsort?
ответ
selection sort is slightly better than quicksort for huge data structures! Откуда вы это взяли? Алгоритм принимает квадратичное время, поэтому он явно намного хуже, чем quicksort. Фактически, как вы собираетесь встраивать 10 ГБ в ОЗУ, вы не можете использовать какой-либо алгоритм для вашего массива, если он не находится в ОЗУ. Вам нужен внешний алгоритм сортировки, или вы можете хранить данные в БД и позволить механизму БД отсортировать его для вас.
Быстрая сортировка лучше для таких огромных данных, как выбор сортировки. Сортировка сортировки может работать лучше в тех случаях, когда тестовые данные имеют более крупные наборы отсортированных данных внутри. Но это никоим образом не делает его лучше, чем быстрый сортировка. Ваша основная проблема в вашем случае заключается в том, как продолжить сортировку таких огромных данных, которые не могут быть сохранены в памяти и выполнены.
Протестировано. Quicksort намного лучше, чем Selectionsort. Я был неправ. правильный выбор был Quicksort, и он отлично работал с изменением доступной памяти (перемещается на 1 ГБ). Спасибо. –