Быстрая сортировка - это найти элемент (изначально вы можете найти его) в качестве ссылки (pivot), а затем разделить массив так, чтобы значение элемента слева от ссылки не было больше эталонного значения, и значение Элемент справа от ссылки не меньше, чем эталонное значение. Рекурсивно быстрая сортировка, отрегулируйте другие элементы N-1 в правильное положение после сортировки. Наконец, каждый элемент находится в правильном положении после сортировки, и сортировка завершена. Следовательно, основным алгоритмом алгоритма быстрой сортировки является операция разделения, то есть как регулировать положение эталона и отрегулировать окончательное положение контрольного эталона, чтобы разделить и завоевать рекурсию.
Алгоритм быстрой сортировки:
1) Установите две переменные i и j, когда сортировка начинается: i = 0, j = n-1;
2) Используйте первый элемент массива в качестве ключа данных и назначьте его клавишу, то есть key = a [0];
3) Начните с j до поиска вперед, то есть начните сзади, чтобы поиск
4) Начните с I до поиска назад, то есть начните спереди к обратному (i ++), найдите первое [i] больше, чем ключ, и поменять a [i] и a [j];
5) Повторите шаги 3 и 4 до i = j; 4 не больше, чем ключ Изменение значений J и I, так что j = j-1, i = i+1, пока оно не найдет. остается неизменным.
Позвольте мне привести вам пример, это может быть нелегко понять. Предположим, что последовательность сортируется
Кода -копия выглядит следующим образом:
пакет com.zc.manythread;
импортировать java.util.random;
/**
* Быстрая сортировка
* @author Administrator
*
*/
открытый класс qsort {
int [] дата;
public qsort (int [] date) {
this.date = date;
}
/**
* Функция обмена
* @param a
* @param i
* @param j
*/
private void swap (int a [], int i, int j) {
int t;
T = a [i];
a [i] = a [j];
a [j] = t;
}
/*************************
* Сортировка функции
* @param a
* @param lo0
* @param hi0
* @возвращаться
*/
int [] QuickSort (int a [], int lo0, int hi0) {// Метод деления и лечения-разделить массив на [lo0..q-1] и [q+1..hi0]
int lo = lo0;
int hi = hi0;
int mid;
if (hi0> lo0) {
mid = a [(hi0+lo0)/2];
while (lo <= hi) {
while ((lo <hi0) && (a [lo] <mid)) ++ lo;
while ((hi> lo0) && (a [hi]> mid)) - -hi;
if (lo <= hi) {
обмен (а, lo, hi);
++ lo;
--привет;
}
}
if (lo0 <hi) {
QuickSort (A, LO0, HI);
}
if (lo <hi0) {
QuickSort (A, LO, HI0);
}
}
вернуть А;
}
/****************
*
* Создание дублирующих данных массива
*******************/
private static int [] censue (int count) {
int [] data = new int [count];
для (int i = 0; i <data.length; i ++) {
data [i] = (int) (math.random ()*count);
}
вернуть данные;
}
/**
* Нет данных о дублирующих массивах
* @param count
* @возвращаться
*/
private static int [] cenectate1 (int count) {
int [] data = new int [count];
Случайный rand = new Random ();
Boolean [] bool = new Boolean [100];
int num = 0;
для (int i = 0; i <count; i ++) {
делать {
// Если сгенерированное число одинаково, продолжайте цикл
num = rand.nextint (100);
} while (bool [num]);
bool [num] = true;
data [i] = num;
}
вернуть данные;
}
/************ Основная функция *******************/
public static void main (string [] args) {
окончательный int count = 10;
int [] data = censueTaite1 (count);
для (int n: data) {
System.out.print (n+"/t");
}
Qsort data1 = new qsort (data);
System.out.println ();
int [] a = data1.quicksort (data, 0, count-1);
для (int n: a) {
System.out.print (n+"/t");
}
}
}
Результаты следующие:
Приведенное выше контент, описанный в этой статье.