По сравнению с такими алгоритмами, как сортировка пузырьков, сортировка выбора и т. Д., Конкретные принципы алгоритма и реализация быстрой сортировки сложны. Чтобы лучше понять быструю сортировку, мы все еще опишем алгоритмические принципы быстрой сортировки подробно в виде примеров. В предыдущем алгоритме сортировки мы будем использовать проблему сортировки высоты 5 спортсменов в качестве примера, чтобы объяснить это. Чтобы лучше отразить характеристики быстрой сортировки, мы добавим здесь еще 3 спортсменов. 8 спортсменов и их информация о росте в этом примере следующие (F, G, H являются новыми спортсменами): A (181), B (169), C (187), D (172), E (163), F (191), G (189), H (182)
В предыдущем алгоритме сортировки все эти сортировки были сделаны тренером. Теперь, когда число спортсменов увеличилось, тренер также хочет воспользоваться возможностью, чтобы сделать перерыв, поэтому тренер позвонил двум помощникам и попросил двух помощников сортировать высоты 8 спортсменов слева направо и низко до высокой до высокой сортировки.
Согласно принципу алгоритма метода быстрой сортировки, два помощника стоят с обеих сторон расположения спортсмена, как показано на рисунке ниже:
Во -первых, помощник 1 выбирает спортсмена из расположения (обычно выбирает первого спортсмена слева или среднего спортсмена), и здесь выбирает спортсмена A (181). Поскольку сортировка слева направо и от низкого до высокого уровня, помощник 1 требует спортсмена, который меньше высоты, чем (181) (выбранная (181) используется в качестве эталона для сравнения. Все сравнения в этом раунде сравниваются с изначально выбранным спортсменом (181)):: Все сравнения сравниваются с первоначально выбранным спортсменом (181))::
Давайте продолжим ссылаться на подробную диаграмму первого раунда быстрой сортировки.
Когда два помощника встречаются в процессе сортировки и поиска, сравнение текущего раунда останавливается, и первоначально выбранный спортсмен A (181) помещается в пустое пространство, где встречаются два помощника:
В быстром роде этот раунд сортировки заканчивается, когда встречаются два помощника. В это время мы обнаружили, что использование позиции A (181), где два спортсмена встретились в качестве точки дивизии, слева - спортсмены, которые меньше, чем (181), а те, которые справа - спортсмены, которые больше, чем А (181). В настоящее время мы разделим два сорта слева и правой стороны (181). Если мы продолжим сортировать соглашения с обеих сторон, используя методы сортировки двух помощников выше, то после нескольких договоренностей мы наконец получим результаты сортировки, которые нам нужны.
Выше приведено весь процесс реализации сортировки быстрой сортировки. Быстрая сортировка заключается в том, чтобы использовать приведенные выше правила сортировки, чтобы разделить расположение на два договоренности, а два договоренности на четыре соглашения до тех пор, пока не будет разделено, и, наконец, мы получаем необходимый результат сортировки.
Теперь мы все еще программируем код Java, чтобы сортировать высоты вышеупомянутых 8 спортсменов, используя быстрый сортировка:
/*** Быстрая сортировка элементов в указанном массиве от начала до конца** @param массив. Указанный массив* @param Начните полученную точку расследования массива, который необходимо быстро сортировать* @param end eder of the Mray Index, который должен быть быстро сортирован*/public static quickort (int, int, int, int, int, int ind {//{//{//{//{//{//{//afent a afent a atempor J эквивалентен позиции помощника 2 int i = start, j = end; int pivot = array [i]; // возьмите первый элемент в качестве эталонного элемента int yumberIndex = i; // указан индекс положения пустого пространства, и по умолчанию является позиция извлекаемого эталонного элемента // Если есть более 1 элемента для сортировки, введите быстрое сортирование (до тех пор, пока я и J различны, это означает, что по крайней мере 2 элемента массива необходимо сортировать), в то время как (i <J) {// Помощник 2 начинает искать элементы меньше, чем ссылочный элемент с правой к левой (I <J) {j) j. if (i <j) {// Если помощник 2 находит соответствующий элемент перед встречей с помощником 1, он дает элемент «вакансиях» помощника 1, J становится пустой космической массией [EmptyIndex] = массив [umptyDex = j]; } // Помощник 1 начинает искать элементы, больше, чем эталонный элемент слева направо (i <j && array [i] <= pivot) i ++; if (i <J) {// Если помощник 1 находит соответствующий элемент перед встречей с помощником 2, он даст элемент «вакансиях» помощника 2, и я стану вакантным массивом [emptyIndex] = массив [emptyIndex = i]; }} // После помощника 1 и ассистента 2 встречи, цикл остановится, и начальное эталонное значение доставляется до последнего вакантного массива [umptyIndex] = pivot; // ===== Этот раунд быстрой сортировки завершен ===== // Если в левой стороне разделенной точки I есть более 2 элементов, рекурсивный вызов продолжает быстро сортировать его, если (i - start> 1) {QuickSort (массив, 0, I - 1); } // Если в правой стороне разделенной точки J более 2 элементов, рекурсивный вызов продолжает быстро сортировать его, если (end - j> 1) {QuickSort (массив, J + 1, End); }} // Основной метод общедоступный статический void main (string [] args) {// ===== Сортировка от низкого до высокого, используя метод быстрой сортировки, чтобы представлять высоты 8 спортсменов ===== // (181), B (169), C (187), D (172), E (163), F (191), g (189), h (182). 187, 172, 163, 191, 189, 182}; // вызовут метод быстрого сортировки QuickSort (Heights, 0, Heights.length - 1); // Вывод сортированный результат для (int height: eights) {System.out.println (Height); }}Приведенные выше результаты запуска кода Java выводятся следующим образом:
163169172181182187189191
Примечание. Из -за локальных различий в мышлении может быть несколько вариантов в приведенной выше реализации быстрого отсортированного кода. Однако, независимо от того, какие варианты, основная идея быстрой сортировки не изменится.
Другая реализация: одностороннее сканирование
Есть еще одна версия для сканирования в одну сторону для быстрого нарезки массива сортировки. Конкретный шаг состоит в том, чтобы выбрать последний элемент в массиве в качестве элемента нарезки и установить два указателя. Указатель I указывает на положение перед первым элементом в массиве, и J указывает на первый элемент в массиве. J сканирует спереди справа и справа. При столкновении с элементом разрезания меньше или равным, добавьте I в один, а затем обменяйте элементы, на которые указывает I и J. Наконец, обменяйте элементы на положении I+1 и нарезными элементами для завершения подразделения массива. Реализация кода выглядит следующим образом:
int partition (int [] a, int lo, int hi) {int i = lo - 1, j = lo; int v = a [hi]; while (j <hi) {if (a [j] <= v) {swap (a, ++ i, j); } j ++; } swap (a, i + 1, hi); вернуть i + 1;}