Быстрый сортировка - это своего рода обмен деления, предложенная Crahoare в 1962 году. Основная идея этого метода такова:
1. Сначала возьмите число из последовательности в качестве эталонного номера.
2. В процессе разделения поместите все числа больше этого числа вправо, и все числа меньше или равны его левой.
3. Повторите второй шаг для левого и правого интервалов, пока в каждом интервале не появится только одно число.
Алгоритм имеет четкую идею, но если граничное значение плохо обрабатывается в течение процесса интервального деления, легко вызвать ошибки. Ниже приведены два более четких мышления, чтобы направлять написание кода интервального разделения.
Первым типом мышления является так называемое мышление копания ямы. Следующее предназначено для анализа процесса метода копания ям, проанализировав пример:
Взяв массив в качестве примера, возьмите первое число в интервале в качестве эталонного номера.
Первоначально, слева = 0; справа = 9; X = a [слева] = 72
Поскольку число в [0] было сохранено в X, его можно понять как копание отверстия в массиве [0], а другие данные могут быть заполнены здесь.
Начните справа и ищите ряд <= x. Очевидно, что когда правый = 8, если условия выполняются, выкопайте [8] и заполните его в предыдущую яму [слева]. Такая яма [0] решается, но образуется новая яма [8]. Что я должен делать? Просто, найдите номер, чтобы заполнить яму A [8]. На этот раз, начните слева и найдите число больше X. Когда слева = 3, соответствуют условиям, выкопайте [3] и заполните его в предыдущей яме A [справа];
Массив становится:
Повторите вышеуказанные шаги, и окончательный массив станет следующей формой:
Видно, что цифры до [5] меньше его, а числа после [5] больше, чем они. Заполните x в яму [5], и данные становится:
Следовательно, повторите вышеуказанные шаги для двух подэтапных A [0… 4] и [6… 9].
Резюме количества выкопанных отверстий
1. I = l; j = r; Выкопайте ссылочный номер, чтобы сформировать первую яму A [i].
2. J-от спины на переднюю часть, найдите число меньше, чем его, выкопайте это число и заполните предыдущую яму A [i].
3. I ++ находит число больше, чем его спереди назад, и после поиска его, выкопайте это число и заполните его в предыдущей яме A [j].
4. Повторите шаги 2 и 3 до i == j, и заполните ссылочный номер в [i].
Следуйте этому методу раздела, код Java быстро отсортируется следующим образом:
Общедоступное разделение класса { / ** * На основе базового деления, маленький находится слева, а большая - справа, и вся последовательность не требуется заказать * * @param ary * @param base * / static void sort (int [] ary, int base) {int left = 0; int right = ary.length - 1; int LewderPoint = слева, правая точка = справа; while (true) {// разделите налево и вправо вправо одновременно для сравнения, слева направо, в то время как (левая точка <правая && ary [Leathpoint ++] <base); // левая точка больше правой или ary [левая точка]> базовая остановка зацикливается на (rightpoint> = левая && ary [rightpoint--]> base); // На противоположной системе. System.out.println («Индекс, который необходимо заменять справа:»+ (правая точка+ 1)); // Два индекса, которые не соответствуют условиям, получены выше, то есть два индекса, которые необходимо заменять, если (левая точка - 1 <правая точка + 1) {// swap (ary, левая точка - 1, правая точка + 1); Util.printarray (ary); левая точка = слева; ПРАВО -точка = справа; } else {break; }}} частное статическое пустое обмен (int [] ary, int a, int b) {int temp = ary [a]; ary [a] = ary [b]; ary [b] = temp; } public static void main (string [] args) {int [] ary = util.generateintarray (10); System.out.println («Оригинальная последовательность:»); Util.printarray (ary); сортировка (ary, 5); System.out.println ("отсортировано:"); Util.printarray (ary); }} результат:
Оригинальная последовательность: [2, 8, 4, 3, 7, 5, 1, 9, 0, 6] Индекс для обмена слева: 1 Индекс для обмена справа: 8 [2, 0, 4, 3, 7, 5, 1, 9, 8, 6] Индекс на обмен слева: 4 Индекс на обмен справа: 6 [2, 0, 3, 1, 5, 7, 9, 8, 6]. Справа: 5 после сортировки: [2, 0, 4, 3, 1, 5, 7, 9, 8, 6]
Еще одно руководящее мышление о интервальном разделении:
Используйте первый элемент массива в качестве значения интервала, разделяйте его от второго элемента, пока не будет сформирован результат, показанный на рисунке.
Затем обменяйте правые граничные значения и t интервала L <T, чтобы сформировать следующий результат:
Таким образом, вы можете написать быстрый код сортировки следующим образом:
public void qsort (int array [], int left, int справа) {if (слева <справа) {int key = array [left]; int high = правильно; int low = слева+1; while (true) {while (low <= high && array [low] <= key) low ++; while (low <= high && array [High]> = key) High--; if (низкий> высокий) разрыв; обмен (массив, низкий, высокий); } swap (массив, слева, высокий); printarray (массив); qsort (массив, слева, High-1); qsort (массив, высокий+1, справа); }}