Сравнение между timsort и quicksort
Почему случается так, что я главным образом слышу о quicksort быть самым быстрым полным алгоритмом сортировки, когда timsort (согласно Википедии), кажется, работают намного лучше? Google, казалось, не поднял вида сравнения.
1 ответ
Tim Sort является великим, если Вам нужен сохраняющий порядок вид, или если Вы сортируете комплексный массив (сравнение основанных на "куче" объектов), а не примитивный массив. Как упомянуто другими, quicksort значительно извлекает выгоду из местности данных и процессора, кэширующегося для примитивных массивов.
то, что худший случай quicksort является O (n^2), было повышено. К счастью, можно достигнуть O (n, регистрируют n), худший случай времени с quicksort. quicksort худший случай происходит, когда точка опоры является или самым маленьким или самым большим значением такой как тогда, когда центр является первым или последним элементом уже сортированного массива.
Мы можем достигнуть O (n, регистрируют n), худший случай quicksort путем установки центра в среднем значении. Начиная с нахождения среднего значения может быть сделан в линейное время O (n). С тех пор O (n) + O (n регистрируют n), = O (n регистрируют n), который становится временной сложностью худшего случая.
На практике, однако, большинство реализаций находит, что случайный центр достаточен, так не ищите среднее значение.