Быстрая сортировка (QSort)(реализация на языке Java)

Java   18 марта 2012  Автор статьи:  

Ниже приведена рекурсивная функция QSort. Функция Main содержит лишь считывание массива и запуск QSort(array,0,n-1) (n — размер массива), поэтому не будет представлена здесь.Хочется отдельно прокомментировать следующий момент. В стандартной реализации в java quicksort выполнял выбор опорного элемента по формуле (l + r) / 2. Но в компании Google при использования данного алгоритма при поиске данных обнаружили проблему с переполнением данных. Условно говоря, если l два миллиарда и r два миллиарда, то при сложении тип данных может кончится и получится какое — то неведомое число, которое потом разделится на 2, поэтому теперь при выборе опорного элемента пишут эквивалентную запись (l + (r — l) / 2), которая не приводит к переполнению.

public static void qSort(int[] array, int l, int r) {
int i = l;
int j = r;
int x = array[l + rand.nextInt(r - l + 1)];
while (i <= j) { while (array[i] < x) { i++; } while (array[j] > x) {
j--;
}
if (i <= j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; i++; j--; } } if (l
Функция создана в том же классе, что и функция Main. В качестве опорного элемента берем элемент с случайным индексом в диапазоне от l до r. Случайный выбор элемента был реализован по причине простоты реализации и хорошей защиты от входных последовательностей, при которых алгоритм будет работать за O(n^2).
Переменная rand имеет тип Random, была проинициализирована как статическая переменная в классе программы и создана в классе Main. Вы можете инициализировать и создавать переменную rand непосредственно в самой функции qSort. Однако ввиду рекурсивности функции переменная rand будет создаваться ровно столько раз, сколько вызываться функция qSort, тем самым быстро съедая процессорное время и память.
Если вы любите пользоваться листами вместо массивов, вот небольшая модификация функции qSort:

public static void qSort(List array) {
int n = array.size();
int i = 0;
int j = n-1;
int x = array.get(rand.nextInt(n));
while (i <= j) { while (array.get(i) < x) { i++; } while (array.get(j) > x) {
j--;
}
if (i <= j) { Collections.swap(array,i,j); i++; j--; } } if (j>0){
qSort(array.subList(0, j + 1));
}
if (i
Из Main вызов происходит просто -- qSort(array).

Научиться программировать

  • на Delphi

  • на Java

  • на C++