В главе 5 вы видели простой метод сортировки под названием
пузырьковая сортировка. Тогда было упомянуто, что есть
значительно лучшие рейтинги. Здесь вы разработаете версию одной из лучших: быструю сортировку (Quicksort).
Быстрая классификация, изобретенная и названная C.A.R. Хоара — лучший алгоритм классификации общего назначения, доступный в настоящее время. Я не смог показать это в главе 5, потому что лучшая реализация быстрой сортировки основана на рекурсии. Версия, которую мы разработаем, сортирует массив символов, но логику можно адаптировать для сортировки объектов любого типа.
Быстрая сортировка основана на идее разделов. Общая процедура включает выбор значения, называемого сравнением, а затем разделение массива на две части. Все элементы, большие или равные значению раздела, вставляются с одной стороны, а меньшие — с другой. Этот процесс повторяется для каждого оставшегося раздела, пока массив не будет отсортирован. Например, при наличии массива Fedacb и использовании значения d в качестве сравнения первый проход быстрой сортировки переупорядочит массив, как показано ниже:

Первоначальное питание
Отрывок 1 b c a d e f

Затем этот процесс повторяется для каждого раздела, то есть bca и def. Как видите, этот процесс по существу рекурсивен, и фактически самая чистая реализация быстрой сортировки является рекурсивной.
Выбрать значение сравнения можно двумя способами. Выбрать его можно случайным образом или найдя среднее значение небольшого набора значений, взятых из массива. Чтобы получить оптимальную классификацию, необходимо выбрать значение, находящееся точно в середине диапазона значений. Однако для большинства наборов данных сделать это непросто. Худший случай — когда выбранное значение находится на одном конце. Несмотря на это, быстрая сортировка будет работать корректно.
Версия быстрой сортировки, которую мы будем разрабатывать, выбирает средний элемент массива для сравнения.

См. QSDemo.java.

Быстрая сортировка:

• Один из наиболее эффективных и широко используемых алгоритмов классификации.
• Изобретено C.A.R. Хоар.
• Основано на концепции разделов, где массив разделен на разделы, которые сортируются рекурсивно.
• Более эффективно, чем пузырьковая сортировка и другие простые методы.

Операция:

• Ценность сравнения (опорная точка):
• Значение выбирается в качестве ссылки (поворотной точки), и массив организуется вокруг этого значения.
• Элементы меньшего размера перемещаются в одну сторону, а более крупные — в другую.
• Процесс повторяется рекурсивно для каждого раздела, пока массив не будет полностью отсортирован.

Быстрая сортировка

QSDemo