Принцип и код реализации Java QuickSort

QuickSort - это обычно используемый, более эффективный алгоритм сортировки, который часто упоминается в процессе собеседования. Давайте подробно объясним его принципы и дадим реализацию версии Java.

Идея быстрой сортировки:

Две независимые части разделены путем сортировки набора элементов данных в одной поездке. Одна часть ключевого слова меньше другой части. Затем сортируйте ключевые слова двух частей один за другим, пока не появится только один независимый элемент, и вся коллекция элементов в порядке.

Процесс быстрой сортировки - метод копания отверстий и чисел заполнения (это очень яркое имя), для набора элементов r [низкий ... высокий], сначала возьмите число (обычно R [Low]) в качестве ссылки и R [низкий] переставляет все элементы в качестве эталона.

Все те, кто меньше, чем r [низкий] расположены спереди, все те, которые больше, чем r [низкий] расположены в задней части, а затем R [низкий] используется в качестве границы, а R [низкий ... высокий] разделены на два подмножества, а затем разделены. До LOW> = высокий.

Например: процесс выполнения быстрой сортировки r = {37, 40, 38, 42, 461, 5, 7, 9, 12} выглядит следующим образом (Примечание: следующая таблица элементов, описанная ниже, начинается с 0):

Начните выбрать базовую основу = 37, таблица ниже низкая = 0, высокая = 8, начиная с высокого = 8, если r [8] <основание, напишите содержание в высоком положении в R [Low], а затем High Положение пустое, низкое = низкое +1;

Начните исследовать с низкого, так как низкий = 1, r [low]> основание, написать R [низкий] до r [высокий], высокий = высокий -1;

Низкий <высокий обнаружен, поэтому первая быстрая сортировка все еще должна продолжаться:

В это время low = 1, высокий = 7, потому что r [высокий] <base, r [High] записывается в r [low], low = low + 1;

Начало обнаружения от низкого, низкого = 2, r [low]> основания, поэтому r [low] записывается в r [High], High = High-1;

Продолжать обнаруживать низкий уровень, меньше, чем высокий

В это время low = 2, high = 6, аналогично, r [высокий] <база, написать r [высокий] до r [low], low = low+1;

Продолжить обнаружить из низкого, низкого = 3, высокого = 6, r [low]> основание, написать r [low] до r [High], High = High-1;

Продолжать обнаруживать, что минимум меньше, чем высокий

В это время low = 3, high = 5, аналогично, r [высокий] <основа, написать r [высокий] в r [low], low = low +1;

Продолжайте исследовать от низкого, низкого = 4, высокого = 5, потому что r [low]> base, запишите r [low] в r [высокий], высокий = высокий -1;

В настоящее время обнаруживается низкий == 4 4;

Затем сделайте быструю сортировку последующих RS1 = {12,9,7,5} и rs2 = {461,42,38,40}, пока в RSI не будет только один элемент или нет.

(Примечание. В приведенной выше форме вы можете видеть, что в сортировке есть некоторые дублирующиеся данные (без дубликатов данных в исходных данных). Это потому, что данные в этом месте не очищены. Мы смотрим на данные памяти Блок в определенное время.

Быстрая сортировка Java реализация:

Кода -копия выглядит следующим образом:

Частный статический логический Isempty (int [] n) {

возврат n == null || n.length == 0;

}

// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ////

/**

* Идея алгоритма быстрой сортировки - метод копания отверстий и заполнения:

*

* @param n массив, чтобы отсортировать

*/

public static void Quicksort (int [] n) {

if (isempty (n))

возвращаться;

Quicksort (n, 0, n.length - 1);

}

public static void Quicksort (int [] n, int l, int h) {

if (isempty (n))

возвращаться;

if (l <h) {

int pivot = раздел (n, l, h);

QuickSort (N, L, Pivot - 1);

Quicksort (n, pivot + 1, h);

}

}

Private Static Int Partition (int [] n, int start, int end) {

int tmp = n [start];

while (start <end) {

while (n [end]> = tmp && start <end)

конец--;

if (start <end) {

n [start ++] = n [end];

}

while (n [start] <tmp && start <end)

start ++;

if (start <end) {

n [end--] = n [Start];

}

}

n [start] = tmp;

вернуть старт;

}

В коде есть такая функция:

Кода -копия выглядит следующим образом:

Public Static Void QuickSortSwap (int [] n, int l, int h)

Эта функция может быть реализована для сортировки элементов данных в элементах, установленных между конкретными позициями L и H.

Это все для быстрой сортировки.