Быстрая сортировка на языке Java
В Java ситуация другая. В ранних версиях не было стандартной функции сортировки, поэтому приходилось писать собственную. В последних версиях появилась такая функция, работающая с классами, реализующими интерфейс Comparable, поэтому теперь мы можем просить библиотеку сортировать то, что нам потребуется. Но поскольку используемые технологии полезны и в других ситуациях, в данном разделе мы опишем все детали реализации быстрой сортировки в Java.
Адаптировать быструю сортировку для каждого конкретного типа данных легко; однако же более поучительно написать обобщенную функцию для сортировки объектов любых типов, что больше похоже на интерфейс qsort.
Одно из крупных отличий от С и C++ заключается в том, что в Java мы
не можем передать функцию сравнения в другую функцию — здесь не существует
указателей на функции. Вместо этого мы создаем интерфейс (interface),
единственным содержимым которого будет функция, сравнивающая два объекта
типа Object. Далее для каждого сортируемого типа данных мы создаем класс
с функцией (методом), которая реализует интерфейс для этого типа данных.
Мы передаем экземпляр класса в функцию сортировки, которая в свою очередь
использует функцию сравнения из этого класса для сравнения элементов.
Сначала опишем интерфейс Стр, который определяет единственную функцию стр, сравнивающую два значения типа Object:
interface Cmp {
int cmp(0bject x, Object y);
}
Теперь мы можем написать функции сравнения, которые реализуют этот интерфейс; например, следующий класс определяет функцию, сравнивающую объекты типа Integer:
а эта функция сравнивает объекты типа St ring:
Данным способом можно сортировать только типы, наследуемые от класса Object;
подобный механизм нельзя применять для базовых типов, таких как int или
double. Поэтому мы сортируем элементы типа Integer,
а не int.
С этими компонентами мы теперь можем перенести функцию быстрой сортировки из языка С в Java и вызывать в ней функцию сравнения из объекта Стр, переданного параметром. Наиболее существенное изменение — это использование индексов left и right, поскольку в Java нет указателей на массивы.
Quicksort.sort использует cmp для сравнения двух объектов, как и раньше, вызывает swap для их обмена.
Генерация случайного номера происходит в функции rand, которая а возвращает
случайное число в диапазоне с left по right включительно:
Мы вычисляем абсолютное значение (используя функцию Math.abs), поскольку
в Java генератор случайных чисел возвращает как положительные, так и отрицательные
значения.
Функции sort, swap и rand, а также объект-генератор случайных чисел rgen являются членами класса Quicksort.
Наконец мы готовы написать вызов Quicksort, sort для сортировки массива типа String:
Так вызывается so rt с объектом сравнения строк, созданным для этой цели.
Упражнение 2-2
Наша реализация быстрой сортировки в Java делает несколько преобразований типов, сначала переводя исходные данные из их первоначального типа (вроде Integer) в Object, а затем обратно. Поэкспериментируйте с версией Quickso rt. so rt, которая использует конкретный тип при сортировке, и попробуйте вычислить, какие потери производительности вызываются преобразованием типов.
