Почему быстрая сортировка лучше, чем слияние?
Мне задавали этот вопрос во время интервью. Они оба O(nlogn), и все же большинство людей используют Quicksort вместо Mergesort. Это почему?
28 ответов
Одна из причин более философская. Быстрая сортировка - это философия Top->Down. С n элементов для сортировки, есть n! возможности. С двумя разделами m & nm, которые являются взаимоисключающими, количество возможностей уменьшается на несколько порядков. м! * (нм)! меньше на несколько порядков чем n! в одиночестве. представь 5! против 3! *2!. 5! имеет в 10 раз больше возможностей, чем 2 раздела по 2 и 3 каждый. и экстраполировать до 1 миллиона факториалов против 900K!*100K! против. Поэтому вместо того, чтобы беспокоиться об установлении какого-либо порядка в пределах диапазона или раздела, просто установите порядок на более широком уровне в разделах и уменьшите возможности внутри раздела. Любой порядок, установленный ранее в пределах диапазона, будет нарушен позже, если сами разделы не являются взаимоисключающими.
Любой подход "снизу вверх", такой как сортировка слиянием или сортировка кучи, похож на подход рабочего или служащего, когда человек начинает сравнивать на микроскопическом уровне рано. Но этот порядок неизбежно будет потерян, как только элемент между ними будет найден позже. Эти подходы очень стабильны и чрезвычайно предсказуемы, но выполняют определенную дополнительную работу.
Быстрая сортировка подобна управленческому подходу, когда изначально никто не заботится о каком-либо заказе, а только о выполнении широкого критерия без учета порядка. Затем разделы сужаются, пока вы не получите отсортированный набор. Настоящая проблема в быстрой сортировке заключается в том, чтобы найти раздел или критерий в темноте, когда вы ничего не знаете об элементах для сортировки. Вот почему мы должны либо потратить некоторое усилие, чтобы найти медианное значение, либо выбрать 1 наугад, либо какой-то произвольный "управленческий" подход. Чтобы найти идеальную медиану, может потребоваться значительное количество усилий и снова привести к глупому подходу снизу вверх. Итак, Quicksort говорит, что нужно просто выбрать случайный шарнир и надеяться, что он будет где-то посередине или поработает, чтобы найти медиану 3, 5 или что-то еще, чтобы найти лучшую медиану, но не планируйте быть идеальным и не тратьте впустую. любое время в первоначальном порядке. Похоже, что это хорошо, если вам повезло или иногда ухудшается до n^2, когда вы не получаете медиану, а просто рискуете. В любом случае данные случайны. право. Так что я больше согласен с логическим подходом сверху -> вниз к быстрой сортировке, и оказывается, что вероятность того, что он удастся отобрать с помощью сводного выбора и сравнений, которые он сохраняет ранее, работает лучше, чем любой дотошный и тщательный стабильный подход снизу вверх> Сортировка слиянием. Но