Предположим, что мы выбираем стержень как первый элемент массива в случае быстрой сортировки. В настоящее время сложнее всего в худшем случае O(n^2), тогда как в среднем случае это O(nlogn). Разве это не странно (лучшая сложность случая больше, чем сложность худшего случая)?Основная путаница в quicksort
Лучшая сложность корпуса O(nlogn), как средний случай. Наихудший случай - O(n^2). Проверьте http://en.wikipedia.org/wiki/Quick_sort.
В то время как другие алгоритмы, такие как Sort Merge Sort and Heap Sort, имеют лучшую в худшем случае сложность (O(nlogn)), обычно Quick Sort быстрее - вот почему это наиболее распространенный использованный алгоритм сортировки. Интересный ответ об этом можно найти по адресу Why is quicksort better than mergesort?.
Лучший случай быстрой сортировки 0(nlogn) - это когда выбранный шарнир разбивает подрамник на две части с одинаковым размером на каждой итерации.
Худший случай быстрой сортировки - это когда выбранный стержень является наименьшим элементом в подмассиве, так что массив разбивается на две части, где одна часть состоит из одного элемента (оси) и другой части всего другого элементы подмассива.
Таким образом, выбирая первый элемент в качестве стержня в уже отсортированном массиве, вы получите 0(n^2). ;)
Поэтому важно выбрать хороший стержень. Например, используя медиану первого, среднего и последнего элемента подмассива, как стержень.
Лучшим случаем является 'O (nlogn)', а не 'O (n^2)'. –