Быстрая сортировка имеет худшую временную сложность, так как O (n^2), в то время как другие, такие как сортировка кучи и сортировка слияния, имеют худшую временную сложность, так как O (n log n) ..если быстрая сортировка считается более быстрой ... Почему ?Почему быстрая сортировка считается самым быстрым алгоритмом сортировки?
На стороне примечания, если сортировка массива целых чисел, то подсчет/радиус сортировки является самым быстрым.
В целом, сортировка слияния делает больше ходов, но меньше сравнивается, чем быстрая сортировка. Типичная реализация сортировки слияния использует массив temp того же размера, что и исходный массив, или 1/2 размера (сортировка второй половины во вторую половину, сортировка первой половины в массиве temp, слияние массива temp + вторая половина в исходный массив) , поэтому для этого требуется больше места, чем быстрая сортировка, которая оптимально требует только уровней вложенности log2 (n), и чтобы избежать вложенности в наихудшем случае, можно использовать проверку вложенности и быструю сортировку для сортировки кучи (это называется introsort).
Если накладные расходы сравнения больше, чем накладные расходы перемещения, то сортировка сортировки выполняется быстрее. Обычный пример, когда сравнение занимает больше времени, чем ходы, будет сортировать массив указателей на строки. Перемещаются только указатели (4 или 8 байт), а строки могут быть значительно больше (и аналогичны для большого количества строк).
Если существует значительный предварительный порядок сортировки данных, то timsort (фиксированные размеры) или «естественный» сортировка слияния (пробеги с переменным размером) будут быстрее.
Хотя это правда, что быстрая сортировка имеет наихудшее время сложность O (N^2), до тех пор, как реализация быстрой сортировки правильно рандомизирует вход, его среднего случая (ожидается) работает время O (N журнала n).
Кроме того, постоянные факторы, спрятанные асимптотической нотацией, которые имеют значение на практике, довольно малы по сравнению с другими популярными вариантами, такими как сортировка слияния. Таким образом, в ожидании, quicksort будет превосходить другие O (n log n) сравнение сортирует, несмотря на менее острые ограничения в худшем случае
Не совсем так. Quicksort является лучшим в большинстве случаев, однако это сложная временная сложность может быть O (n^2), это не значит, что это всегда так. Проблема заключается в выборе правильной точки поворота, если вы правильно ее выбрали, у вас есть сложность времени O (n log n). Кроме того, quicksort является одним из самых дешевых/самых простых в реализации.
См. [Это] (http://cs.stackexchange.com/questions/3/why-is-quicksort-better-than-other-sorting-algorithms-in-practice) – Sait
Могу ли я узнать причину .. Почему мой вопрос отклонен, так что я буду заботиться об этом в будущем? – Himanshu
Да. Я предполагаю, что это отклонено, потому что (1) вопрос слишком широк (2) вы не показываете какую-либо работу, которую вы выполнили (например, поиск по одному и тому же вопросу и чтение веб-страницы, задание более конкретного вопроса после прочтения более подробно об этом или написать фрагмент кода и проанализировать различные алгоритмы сортировки по различным сценариям, затем задать вопрос о вашем коде и т. д.). Также прочитайте [как-спросить] (http://stackoverflow.com/help/как к спрашивать). – Sait