Вид улучшения в сортировке пузырьков состоит в том, что если первичная последовательность записи упорядочена или в основном упорядочена ключевыми словами, она вырождается в пузырьковую сортировку. Принцип рекурсии используется, и его средняя производительность лучше всего среди всех методов сортировки того же порядка величины (n longn). С точки зрения среднего времени, в настоящее время он считается лучшим методом внутренней сортировки.
Основная идея: разделите данные, которые должны быть отсортированы на две независимые части путем сортировки лжи, и все данные частично меньше, чем все данные в другой части, а затем быстро сортируют эти две части данных в соответствии с этим методом .
Три указателя: Первый указатель называется указателем Pivotkey (Pivot), второй указатель и третий указатель - левый указатель и правый указатель, соответственно, указывающие на самое левое значение и самое правое значение. Левый указатель и правый указатель подходят с обеих сторон к середине одновременно. Поворота до более высокого уровня.
Требуются две функции:
① Рекурсивная функция общедоступная статическая пустота Quicksort (int [] n, int left, int right)
② Функция сегмента (одна функция быстрой сортировки) Общественный статический раздел int (int [] n, int left, int right)
Исходный код Java (успешно запустите):
Кода -копия выглядит следующим образом:
Пакет TestSortalGorithm;
публичный класс QuickSort {
public static void main (string [] args) {
int [] array = {49,38,65,97,76,13,27};
QuickSort (массив, 0, массив. Length - 1);
для (int i = 0; i <array.length; i ++) {
System.out.println (Array [i]);
}
}
/*Сначала запишите алгоритм в качестве прототипа данных в соответствии с массивом, а затем напишите алгоритм масштабируемости. Массив {49,38,65,97,76,13,27}}
* */
public static void Quicksort (int [] n, int left, int right) {
int pivot;
if (слева <справа) {
// Поворотка в качестве поворота, меньший элемент слева, а более крупный элемент справа
pivot = раздел (n, слева, справа);
// рекурсивно вызовать быстрое сортировка слева и правые массивы, пока заказ не будет полностью правильным
Quicksort (n, слева, pivot - 1);
QuickSort (n, pivot + 1, справа);
}
}
public static int partition (int [] n, int left, int справа) {
int pivotkey = n [слева];
// Пивот никогда не изменится после выбора, и в конечном итоге он будет посередине, с маленькой передней и большой спиной
while (слева <справа) {
while (слева <rugh && n [справа]> = pivotkey) -Пряга;
// Переместите элемент меньше, чем поворот до низкого уровня.
n [слева] = n [справа];
while (слева <правый && n [слева] <= pivotkey) ++ слева;
// Переместите элемент больше, чем поворот до высокого уровня.
n [справа] = n [слева];
}
// Когда влево == ПРАВО, завершите быструю сортировку.
n [слева] = pivotkey;
вернуться влево;
}
}