Быстрая сортировка. 
Рекурсия как способ организации обработки данных

Быстрая сортировка (англ. quicksort) — это надежный и эффективный алгоритм сортировки, который используется не только для учебных целей, но и широко применяется на практике. Быстрая сортировка также называется сортировкой Хоара по имени автора алгоритма Чарльза Хоара. Для большинства массивов этот метод требует приблизительно обменов элементов и сравнений, то есть намного меньше, чем любой другой элементарный метод сортировки. Метод основан на подходе «разделяй и властвуй». Идея алгоритма достаточна проста. Из массива выбирается некоторый опорный элемент р, вокруг которого перемещаются все элементы. Причем элементы меньшие, либо равные р, перемещаются влево от него, а элементы большие, либо равные р — вправо. Далее метод быстрой сортировки рекурсивно запускается для каждой из частей массива. Алгоритм имеет наименьшее время сортировки, если в качестве опорного элемента выбирается средний по номеру элемент, так как в результате разделения части массива имеют одинаковые размеры.

Задача 6.6 Напишите рекурсивный метод быстрой сортировки целочисленного массива.

Объяснение: введем два индекса i и j, в начале алгоритма они указывают, соответственно, на левый и правый конец последовательности. Начнем двигать указатель i с шагом 1 по массиву вперед, пока не будет найден элемент со значением большим или равным значению опорного элемента. Затем аналогичным образом двигаем указатель j от конца массива к началу, пока не будет найден элемент со значением меньшим или равным значению опорного элемента. Далее, если i<=j, меняем найденные элементы местами и продолжаем двигать i и j. Алгоритм разделения заканчиваем тогда, когдаиндекс i становиться больше индекса j. После разделения все значения до индекса i меньше или равны опорному элементу, а все значения после индекса j больше или равны опорному элементу. Далее рекурсивно вызываем метод быстрой сортировки отдельно для каждой из частей массива. Пример выполнения алгоритма быстрой сортировки массива {5, 0, -10, 9, 15, 100, -12, 3} иллюстрирует рис. 6.5. На рисунке показан только первый шаг рекурсии. На самом деле подмассивы {5, 0, -10, 3, -12} и {100, 15, 9} сортируются затем рекурсивно. Условием завершение рекурсивных вызовов является наличие одного элемента в каждой из частей массива.

public class QuickSort {.

static void quickSort (int[] a, int left, int right) {.

int i=left, j=right;

int p=a[(left+right)/2]; //опорный элемент.

int tmp;

// разделение.

do {.

while (a[i].

while (a[j]>p) j—;

if (i<=j) {.

tmp=a[i]; a[i]=a[j]; a[j]=tmp;

i++; j—;

}.

} while (i<=j);

// рекурсивные вызовы сортировки.

if (j>left) quickSort (a, left, j);

if (i.

}.

public static void main (String[]args) {.

int[] a = {5,0,-10,9,15,100,-12,3};

quickSort (a, 0, a. length-1);

System.out.println (java.util.Arrays.toString (a));

}}.

Результат:

[-12, -10, 0, 3, 5, 9, 15, 100].

Рис. 6.5 — Демонстрация выполнения алгоритма быстрой сортировки