1. Обзор
Сортировка и поиск — две основные проблемы программирования, и существует множество классических алгоритмов, используемых для решения этих двух типов проблем. В этой статье в основном проводится базовое обсуждение реализации алгоритмов сортировки в Java, надеясь послужить отправной точкой. роль. Перед этим позвольте мне сначала задать вам несколько вопросов: можете ли вы написать правильную быструю сортировку? При каких обстоятельствах быстрая сортировка действительно быстрая? Ваша быстрая очередь достаточно быстрая? Можно ли его оптимизировать дальше? Ответив на эти вопросы, давайте посмотрим, как в jre7 реализована быстрая сортировка.
Класс реализации сортировки в Jre7 — DualPivotQuickSort.java. По сравнению с jre6 есть некоторые изменения, в основном в двух местах: один — это реализация сортировки вставками, а другой — изменение точки поворота с одного на два. . В качестве примера возьмем массив типа int. В этом классе есть основной метод сортировки. Прототипом этого метода является.
Скопируйте код кода следующим образом:
void sort(int[] a, int left, int right, логическое значение слева)
Параметр a — это массив, который необходимо отсортировать, left представляет индекс самого левого элемента в диапазоне массива, который необходимо отсортировать, right представляет индекс самого правого элемента в диапазоне, а самый левый указывает, является ли диапазон самым левым. диапазон в массиве. Например:
Массив: [2, 4, 8, 5, 6, 3, 0, -3, 9] можно разделить на три интервала (2, 4, 8){5, 6<3, 0, -3, 9>
Для интервала () левый=0, правый=2, крайний левый=истина
Для интервала {}, left=3, right=4, leftmost=false соответствующие параметры интервала <> можно получить таким же образом.
Если длина интервала меньше 47, этот метод будет использовать сортировку вставками, в противном случае будет использоваться быстрая сортировка.
2. Реализация сортировки вставками
Если значение «крайний слева» истинно, будет использоваться традиционная сортировка вставкой, и код относительно прост. Процесс аналогичен захвату и вставке карт при игре в карты:
Скопируйте код кода следующим образом:
for (int i = left, j = i; i < right; j = ++i) {
int ai = a[i + 1];
в то время как (ai < a[j]) {
а[j + 1] = а[j];
если (j-- == слева) {
перерыв;
}
}
а[j + 1] = ай;
}
Традиционный код сортировки вставкой
Когда значение «крайний левый» имеет значение «ложь», используется новый тип сортировки вставкой (парная сортировка вставкой). Улучшение заключается в том, что каждый раз, когда он проходит по ранее отсортированному массиву, необходимо вставить два элемента, в то время как традиционная сортировка вставкой требует только «Найти подходящее место для». элемент для вставки. Для сортировки вставкой ключевой момент — найти подходящую позицию вставки для вставляемого элемента. Чтобы найти эту позицию, необходимо пройти по ранее отсортированному подмассиву, поэтому для сортировки вставкой — по элементам, которые он пересекает в течение всей сортировки. процесс Число определяет его производительность. Очевидно, что вставка двух элементов при каждом обходе может уменьшить количество элементов, проходимых в процессе сортировки. Код реализации выглядит следующим образом:
Скопируйте код кода следующим образом:
for (int k = влево; ++left <= вправо; k = ++left) {
int a1 = a[k], a2 = a[left];
если (а1 < а2) {
а2 = а1; а1 = а[слева];
}
в то время как (a1 < a[--k]) {
а[к + 2] = а[к];
}
а[++к + 1] = а1;
в то время как (a2 < a[--k]) {
а[к + 1] = а[к];
}
а[к + 1] = а2;
}
Теперь возникает вопрос: почему в крайнем левом диапазоне используется традиционная сортировка вставками, а в остальных — попарная сортировка? Какие проблемы возникнут, если мы заменим традиционный код сортировки вставками приведенным выше кодом попарной сортировки вставками? Надеюсь, вы сами ответите на этот вопрос. . .
3. Реализация быстрой сортировки
Быстрая сортировка также была улучшена в Jre7. Традиционная быстрая сортировка выбирает опорную точку (методы выбора опорной точки в jre6 заключаются в выборе элементов в крайнем левом, среднем и крайнем правом положении массива и ранжировании элементов со средними значениями как поворот), а затем пройдите от обоих концов к середине и поместите объекты, встреченные во время левого обхода Значение, большее, чем точка поворота, заменяется значением, меньшим или равным точке поворота, встречающейся при обходе справа. Когда обход встречается, значение точки поворота вставляется, что делает значения слева от точки поворота меньше или; равно Pivot, а значение справа от Pivot больше, чем Pivot. Далее используйте рекурсию для сортировки левой и правой сторон соответственно;
Благодаря приведенному выше анализу мы видим, что: каждый шаг сортировки вставкой заключается в том, чтобы сделать поддиапазон массива абсолютно упорядоченным, а суть каждого цикла заключается в постоянном расширении этого поддиапазона, поэтому мы видим, что направление оптимизации состоит в том, чтобы make При каждом обходе цикла поддиапазон расширяется как можно быстрее, поэтому оптимизирована описанная выше оптимизация вставки одного элемента за проход во вставку двух элементов за раз. Конечно, кто-то обязательно спросит, а почему бы не увеличить это число? Например, 5 или 10 вставляются при каждом прохождении. . . Очевидно, что это невозможно. Крайним случаем является вставка n элементов (n — длина массива) при каждом его обходе. . . А почему, каждый может ответить сам.
Для быстрой сортировки каждая рекурсия делает поддиапазоны, которые необходимо отсортировать, более упорядоченными, а не абсолютно упорядоченными; поэтому для быстрой сортировки ее производительность зависит от того, как каждая рекурсивная операция делает сортируемый поддиапазон более упорядоченным. Определяющим фактором того, насколько упорядочен подинтервал, является, конечно же, количество рекурсий. Ключом к быстрой сортировке, позволяющей сделать подинтервал относительно упорядоченным, является центр поворота, поэтому направление нашей оптимизации также должно быть центром поворота. Затем увеличьте количество поворотов, и мы обнаружим, что увеличение количества поворотов не влияет на количество поворотов. рекурсии Это окажет большое влияние, а иногда даже может уменьшить количество рекурсий. Аналогичный вопрос для сортировки вставкой: сколько поворотов следует увеличить? Очевидно, что значение пивота не может быть слишком большим; помните, любая оптимизация имеет стоимость, а стоимость увеличения пивота каждый раз скрыта в процессе смены положения элементов. Гуаньцзы, кажется, продается слишком дорого. . . Давайте посмотрим, как реализуется быстрая сортировка, когда значение поворота равно 2. Процесс его реализации на самом деле понять несложно:
1. Сначала выберите две опорные точки. Метод выбора опорной точки состоит в том, чтобы разделить массив на шесть сегментов одинаковой длины. Эти шесть сегментов фактически разделены 5 элементами. 4-й — Pivot1 и Pivot2 соответственно;
2. После выбора точки поворота перемещение слева и справа заканчивается к середине. Условием остановки для перемещения влево является обнаружение значения, большего или равного значению поворота 1, и пометка этого положения как меньшее. обход состоит в том, чтобы встретить значение, меньшее или равное значению Pivot2, и пометить эту позицию как большую
3. Затем переместите назад из меньшего положения. Пройденное положение обозначается буквой k. Вы можете столкнуться со следующими ситуациями:
а. Если значение позиции k меньше значения Pivot1, поменяйте местами значения позиции k и позиции less и прибавьте 1 к значению less, это сделает значения слева от позиции; Меньшая позиция меньше, чем Pivot1, и значения между Меньшей позицией и K-позицией будут Значение больше или равно Pivot1.
б. Если значение в позиции k больше, чем значение Pivot2, то перейти от большой позиции влево. Условием остановки перемещения является обнаружение значения, меньшего или равного Pivot2. Если это значение меньше, чем Pivot1, запишите. это значение в меньшую позицию и записываем значение в меньшую позицию. Значение записывается как позиция k, а значение позиции k записывается как большая позиция, и, наконец, less++, great--; чтобы оно было больше или равно Pivot1, поменяйте местами позицию k и позицию Great, а затем
4. После завершения описанного выше процесса отсортированный подинтервал делится на три сегмента (<pivot1, Pivot1<=&&<=pivot2,>pivot2). Наконец, для этих трех сегментов используется рекурсия.
Скопируйте код кода следующим образом:
/*
*Разделение:
*
* левая часть, центральная часть, правая часть
* +---------------------------------------------------------------- ---------------+
* | < опорная точка1 | опорная точка1 <= && <= опорная точка2 |
* +---------------------------------------------------------------- ---------------+
* ^ ^ ^
* |
* меньше k отлично
*
*Инварианты:
*
* все внутрь (слева, меньше) < Pivot1
* Pivot1 <= все в [меньше, k) <= Pivot2
* все включено (отлично, верно) > Pivot2
*
* Указатель k — это первый индекс ?-части.
*/
Основное содержание реализации сортировки в Jre7 указано выше. Для получения более подробной информации обратитесь к коду соответствующего класса. Если вы обнаружите какие-либо ошибки или неточности, исправьте их.