Важным фактом, который вы должны знать, является то, что в массиве различных элементов быстрая сортировка со случайным выбором раздела будет выполняться в O (n lg n). Есть много хороших доказательств этого, и тот, что в Википедии , на самом деле довольно неплохо об этом говорит. Если вы хотите получить немного менее формальное доказательство, которое в основном математически обосновано, интуиция выглядит следующим образом. Всякий раз, когда мы выбираем опорную точку, скажем, что «хорошая» опорная точка - это опорная точка, которая дает нам как минимум 75% / 25% сплит; то есть, это больше, чем как минимум 25% элементов и самое большее 75% элементов. Мы хотим ограничить число раз, когда мы можем получить такой поворот, прежде чем алгоритм завершится. Предположим, что мы получили k разбиений такого рода и рассмотрим размер наибольшей подзадачи, сгенерированной таким образом. Его размер не более (3/4) k n, поскольку на каждой итерации мы избавляемся как минимум от четверти элементов. Если мы рассмотрим конкретный случай, когда k = log 3/4 (1 / n) = log 4/3 n, то выбирается размер наибольшей подзадачи после k хороших опорных точек будет 1, и рекурсия остановится. Это означает, что если мы выберем O (LG N) хороших точек, рекурсия завершится. Но на каждой итерации, каков шанс получить такой стержень? Что ж, если мы выберем пивот случайно, то есть 50% -ная вероятность, что он находится в середине 50% элементов, и поэтому мы ожидаем, что мы выберем два случайных пивота, прежде чем получим хороший пивот. Каждый шаг выбора точки разворота занимает время O (n), и поэтому мы должны потратить примерно O (n) времени, прежде чем получить каждый хороший разворот. Поскольку мы получаем не более O (lg n) хороших точек, общее время выполнения при ожидании составляет O (n lg n).
Важной деталью в приведенном выше обсуждении является то, что если вы замените 75% / 25% -ое разделение на любое постоянное разделение - скажем, (100 - k%) / k% -разложение - анализ асимптотики будет таким же. Вы получите, что быстрая сортировка занимает в среднем O (n lg n) время.
Причина, по которой я упомянул это доказательство, состоит в том, что оно дает вам хорошую основу для размышлений о том, как выбрать сводную точку в быстрой сортировке. Если вы можете выбрать точку поворота, которая довольно близка к середине, на каждом этапе, вы можете гарантировать время выполнения O (n lg n). Если вы не можете гарантировать, что вы получите хорошую сводку на любой итерации, но можете сказать, что в ожидании потребуется только постоянное число итераций, прежде чем вы получите хорошую сводку, тогда вы также можете гарантировать O (n lg n) ожидаемое время выполнения.
Учитывая это, давайте посмотрим на ваши предложенные схемы разворота. Для (a), если массив является случайным, выбор первого элемента в качестве сводного элемента по существу аналогичен выбору случайного поворотного элемента на каждом шаге, и поэтому с помощью приведенного выше анализа вы получите O (n lg n) времени выполнения в ожидании , Для (б), если вы знаете, что массив в основном отсортирован, то выбор медианы является хорошей стратегией. Причина в том, что если мы можем сказать, что каждый элемент «довольно близок» к тому месту, где он должен быть в отсортированной последовательности, то вы можете аргументировать, что каждый выбранный вами стержень является хорошим стержнем, давая вам O (n lg n). ) время выполнения вы хотите. (Термин «довольно близко» не очень математически точен, но я думаю, что вы могли бы формализовать это без особых затруднений, если бы захотели).
Что касается (c) и (d), из двух, (d) является единственным, который гарантированно получит O (n lg n) в ожидании. Если вы детерминистически выберете определенные элементы для использования в качестве опорных точек, ваш алгоритм будет уязвим для детерминированных последовательностей, которые могут выродить его в поведение O (n 2 ). На самом деле есть очень интересная статья на эту тему под названием «Убийца-убийца для быстрой сортировки» , написанная Макилрой, в которой описывается, как вы можете взять любую детерминированную быструю сортировку и построить для нее патологически наихудший случай, используя вредоносную функцию сравнения. Вы почти наверняка захотите избежать этого в любой реальной реализации быстрой сортировки, поскольку в противном случае злонамеренные пользователи могут запускать DoS-атаки на ваш код, передавая эти убийственные последовательности, чтобы заставить вашу программу сортироваться в квадратичном времени и, таким образом, зависать. С другой стороны, поскольку (d) выбирает точки выборки случайным образом, он не уязвим для этой атаки, потому что в любой последовательности выбор точек разворота является случайным.
Интересно, однако, что для (d), хотя не больно выбирать три случайных элемента и брать медиану, вам не нужно это делать. Предыдущих доказательств достаточно, чтобы показать, что вы получите O (n lg n) по ожиданию с одним случайным выбором пивота. Я на самом деле не знаю, улучшит ли выбор медианы из трех случайных значений производительность алгоритма быстрой сортировки, хотя, поскольку быстрая сортировка всегда & Omega; (n lg n), она определенно не будет асимптотически лучше, чем просто выбор случайных элементов как стержни.
Я надеюсь, что это немного поможет - мне очень нравится алгоритм быстрой сортировки и все конструктивные решения, связанные с созданием хорошей реализации быстрой сортировки. : -)