Java руководство для начинающих - Шилдт Герберт (2012)

В главе 5 был рассмотрен простой способ так называемой пузырьковой сортировки, а кроме него, вкратце упоминались и более совершенные способы сортировки. В этом проекте предстоит реализовать один из самых лучших способов: быструю сортировку. Алгоритм быстрой сортировки был разработан Ч. Хоаром и назван его именем. На сегодняшний день это самый лучший универсальный алгоритм сортировки. Он не был продемонстрирован в главе 5 лишь потому, что реализовать быструю сортировку лучше всего с помощью рекурсии. В данном проекте будет создана программа для сортировки символьного массива, но демонстрируемый подход может быть применен к сортировке любых объектов.

Быстрая сортировка опирается на принцип разделения. Сначала выбирается опорное значение (так называемый компаранд), и массив разделяется на две части. Все элементы, которые больше или равны разделяемому компаранду, помещаются в одну часть массива, а те элементы, которые меньше компаранда, — в другую часть. Затем процесс рекурсивно повторяется для каждой оставшейся части до тех пор, пока массив не окажется отсортированным. Допустим, имеется массив, содержащий последовательность символов f edacb, а в качестве компаранда выбран символ d. На первом проходе массив будет частично упорядочен следующим образом:

Исходные данные

f e d a с b

Проход 1

b с a d e f

Этот процесс повторяется для каждой части: Ьса и def. Как видите, процесс рекурсивен по своей сути, поэтому рекурсивный способ лучше всего подходит для реализации быстрой сортировки.

Компаранд можно выбрать двумя способами: случайно либо вычислив среднее значение части элементов массива. Эффективность сортировки окажется оптимальной в том случае, когда компаранд выбран как раз посредине диапазона значений элементов, содержащихся в массиве, но зачастую выбрать такое значение непросто. Если же выбрать компаранд случайным образом, то вполне возможно, что он окажется на краю диапазона. Но и в этом случае алгоритм быстрой сортировки будет действовать правильно. В том варианте быстрой сортировки, который реализуется в данном проекте, в качестве компаранда выбирается элемент, находящийся посередине массива.

Последовательность действий

Создайте новый файл QSDemo. j ava.

Создайте сначала класс Quicksort, код которого приведен ниже.

// Пример для опробования 6.3. Простая версия класса Quicksort,

// реализующего быструю сортировку,

class Quicksort {

// организовать вызов конкретного метода быстрой сортировки

static void qsort(char items[]) {

qs(items, 0, items.length-1);

}

// Рекурсивная версия метода быстрой сортировки символов,

private static void qs(char items[], int left, int right)

{

int i, j;

char x, y;

i = left; j = right;

x = items[(left+right)/2];

do {

while((items[i] < x) && (i < right)) i++;

while((x < items[j]) && (j > left)) j—;

if(i <= j) {

у = items[i];

items[i] = items[j];

items[j] = y;

i++; j—;

}

} while (i <= j);

if(left < j) qs(items, left, j);

if(i < right) qs(items, i, right);

}

}

Для упрощения интерфейса в классе Quicksort предоставляется метод qsort (), из которого вызывается метод qs (), фактически выполняющий сортировку. Такой подход позволяет выполнять сортировку, передавая методу лишь имя массива и не осуществляя первоначальное разделение. А поскольку метод qs () используется только в классе, он определяется как private.