Быстрая сортировка широко используется в качестве эффективного алгоритма сортировки. Метод Arrays.sort в SUN JDK использует быструю сортировку.
Быстрая сортировка использует классическую идею «разделяй и властвуй»:
Разделить: выберите примитив X (обычно первый элемент массива) и разделите массив на две части с помощью некоторой операции разделения: левая половина меньше или равна X, а правая половина больше или равна X. .
Conquer: левый и правый подмассивы рекурсивно вызывают процесс Divide.
Объединение. Быстрая сортировка используется в качестве алгоритма сортировки по месту и не требует каких-либо операций слияния.
Видно, что основной частью быстрой сортировки является процесс разделения. Ниже приведен пример, подробно объясняющий, как разделить массив (изображение взято из «Введение в алгоритмы»).
Инициализация: выберите примитив P=2, который является первым элементом массива. i=1,j=i+1=2 (индекс массива начинается с 1)
Инвариант цикла: все элементы между 2~i меньше или равны P, а все элементы между i+1~j больше или равны P.
Циклический процесс: j переходит от 2 к n, проверяется элемент в позиции j и, если он больше или равен P, продолжает цикл. Если оно меньше P, поменяйте местами элементы в позиции j (которые не должны появляться в диапазоне i+1~j) на элементы в позиции i+1 (все еще находящиеся в диапазоне i+1~j после замены), и в то же время измените i+1 . Это сохранит инварианты цикла (см. описание инвариантов цикла выше). Пока j=n, последняя операция цикла завершается.
Следует отметить, что после завершения цикла элемент в позиции i необходимо заменить на первый элемент массива, чтобы он соответствовал требованиям, которые мы сначала установили (соответствует i-му шагу на рисунке).
Внимательные читатели могут подумать о другом, более простом методе разделения, то есть извлечении примитивов и сохранении их в другом массиве того же размера. При обнаружении элементов, меньших, чем примитивы, они сохраняются в левой половине массива. элементы, превышающие примитивы, хранятся в левой половине массива. Элементы хранятся в правой половине массива. Сложность таких операций также линейна, а именно Theta(n). Но космическая сложность удваивается. Это также преимущество быстрой сортировки на месте.
Скопируйте код кода следующим образом:
общественный класс QuickSort {
Private static void QuickSort (массив int [], начало int, конец int)
{
если (начало <конец)
{
int key=array[start];//Инициализируем и сохраняем примитивы
int i=start,j;//Инициализируем i,j
for(j=start+1;j<=end;j++)
if(array[j]<key)//Если элемент здесь меньше примитива, замените этот элемент элементом с номером i+1 и добавьте 1 к i. Если он больше или равен примитиву, продолжайте. петля.
{
интервал темп = массив [j];
массив[j]=массив[я+1];
массив[я+1]=температура;
я++;
}
}
array[start]=array[i];//Обмен элементами и примитивами в i
массив [я] = ключ;
QuickSort(array, start, i-1);//рекурсивный вызов
QuickSort(массив, я+1, конец);
}
}
public static void main(String[] args)
{
int[] array=new int[]{11,213,134,44,77,78,23,43};
QuickSort(массив, 0, массив.длина-1);
for(int i=0;i<array.length;i++)
{
System.out.println((i+1)+"th:"+array[i]);
}
}
}