Быстрая сортировка (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), которая не приводит к переполнению.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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<j){
            qSort(array, l, j);
        }
        if(i<r){
            qSort(array, i, r);
        }
    }

Функция создана в том же классе, что и функция Main. В качестве опорного элемента берем элемент с случайным индексом в диапазоне от l до r. Случайный выбор элемента был реализован по причине простоты реализации и хорошей защиты от входных последовательностей, при которых алгоритм будет работать за O(n^2).
Переменная rand имеет тип Random, была проинициализирована как статическая переменная в классе программы и создана в классе Main. Вы можете инициализировать и создавать переменную rand непосредственно в самой функции qSort. Однако ввиду рекурсивности функции переменная rand будет создаваться ровно столько раз, сколько вызываться функция qSort, тем самым быстро съедая процессорное время и память.
Если вы любите пользоваться листами вместо массивов, вот небольшая модификация функции qSort:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 public static void qSort(List<Integer> 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<n){
            qSort(array.subList(i,n));
        }
    }

Из Main вызов происходит просто — qSort(array).

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

  • на Delphi

  • на Java

  • на C++