быстрая сортировка медленнее сортировки слиянием

Question

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

Answer 1

Схема разделов Lomuto, которая сканирует от одного конца к другому во время раздела, медленнее с дубликатами.Если все значения одинаковы, то каждый шаг разбиения разбивает его на размеры 1 и n-1, в худшем случае.

Схема разбиения Hoare, которая сканирует оба конца друг к другу, пока индексы (или итераторы, или указатели) не пересекаются, обычно быстрее с дубликатами.Несмотря на то, что дубликаты приводят к большему количеству свопов, каждый своп происходит сразу после чтения и сравнения двух значений с осью и остается в кеше для свопа (при условии, что размер объекта невелик).По мере увеличения числа дубликатов разделение улучшается в идеальном случае, когда каждый шаг разделения разделяет данные на две равные половины.Я выполнил тестирование сортировки 16 миллионов 64-битных целых чисел: со случайными данными это заняло около 1,37 секунды, улучшение с дубликатами и со всеми одинаковыми значениями - около 0,288 секунды.

Другой вариант - 3раздел, который разбивает раздел на элементы pivot.Если все элементы одинаковы, это делается за O (n) времени.Для n элементов, имеющих только k возможных значений, сложность по времени равна O (n ⌈log3 (k) ⌉), а поскольку k постоянна, сложность по времени по-прежнему составляет O (n).

Вики-ссылки:

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

https://en.wikipedia.org/wiki/Dutch_national_flag_problem