Для каких входных данных хороши / плохи следующие алгоритмы сортировки?

Question

Для какого типа ввода данных эффективны / не эффективны следующие алгоритмы сортировки?Quicksort, Mergesort, Heapsort, Insertion sort и т. Д.

Я знаю, что как минимум 2 фактора влияют на производительность алгоритма сортировки: 1) размер входных данных и 2) независимо от того, являются ли данныеуже в основном отсортировано.Но я не знаю точно, как эти факторы влияют на эффективность алгоритмов.

Я хотел бы изучить это подробно, поэтому, если есть какие-либо источники / ссылки, на которые вы можете указать мне, это 'буду великолепен.

Answer 1

Если предположить, что быстрая сортировка основана на схеме разбиения Хоара (среднее значение как опорная точка), то это не приведет к ухудшению временной сложности O (n ^ 2) для почти отсортированных данных.

https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

Mergesort всегда делает n ⌈log2 (n) ⌉ ходов.Если данные уже отсортированы, то число сравнений составляет около (⌈n ⌈log2 (n) ⌉) /2.

Сложность времени в Heapsort остается примерно такой же (дубликаты могут сократить время выполнения).

Сортировка вставок - это единственная сортировка в этом списке, которая выполняется быстрее, если данные почти отсортированы, но сложность по времени равна O (n ^ 2).Я думаю, что для почти отсортированных данных временная сложность будет ~ O (mn), где m - количество элементов не к месту.

Вариации естественной сортировки слиянием, которые могут использовать вставку сортировки нанебольшие прогоны при сканировании и идентификации уже отсортированных прогонов будут иметь сложность по времени O (n) для уже отсортированных данных.