Временная сложность гибридного алгоритма QuickSort + Insertion sort?

Question

Я реализую алгоритм, который выполняет быструю сортировку с выбором крайнего левого поворота до определенного предела, и когда список массивов становится почти отсортированным, я буду использовать сортировку вставкой для сортировки этих элементов.

Для выбора самого левого поворота я знаю, что средняя сложность быстрой сортировки равна O (nlogn), а сложность наихудшего случая, т.е. когда список почти отсортирован, равна O (n ^ 2).С другой стороны, сортировка вставкой очень эффективна для почти отсортированного списка элементов со сложностью O (n).Так что я думаю, что сложность этого гибридного алгоритма должна быть O (n).Я прав?

Answer 1

Самая важная вещь для производительности qsort - это выбор хорошей точки опоры прежде всего.Это означает, что вы выбираете элемент, максимально приближенный к среднему значению элементов, которые вы сортируете.

Худший случай O (n ² ) в qsort возникает из-за последовательного выбора 'Плохо поворачивается каждый раз для каждого прохода раздела.Это приводит к тому, что перегородки будут чрезвычайно односторонними, а не сбалансированными, например.Соотношение элементов 1: n-1.

Я не вижу, как добавление сортировки вставок в микс, как вы описали, помогло бы или смягчило эту проблему.