Быстрая сортировка на языке Java
В Java ситуация другая. В ранних версиях не было стандартной функции сортировки, поэтому приходилось писать собственную. В последних версиях появилась такая функция, работающая с классами, реализующими интерфейс Comparable, поэтому теперь мы можем просить библиотеку сортировать то, что нам потребуется. Но поскольку используемые технологии полезны и в других ситуациях, в данном разделе мы опишем все детали реализации быстрой сортировки в Java.
Адаптировать быструю сортировку для каждого конкретного типа данных легко; однако же более поучительно написать обобщенную функцию для сортировки объектов любых типов, что больше похоже на интерфейс qsort.
Одно из крупных отличий от С и C++ заключается в том, что в Java мы не можем передать функцию сравнения в другую функцию – здесь не существует указателей на функции. Вместо этого мы создаем интерфейс (interface), единственным содержимым которого будет функция, сравнивающая два объекта типа Object. Далее для каждого сортируемого типа данных мы создаем класс с функцией (методом), которая реализует интерфейс для этого типа данных. Мы передаем экземпляр класса в функцию сортировки, которая в свою очередь использует функцию сравнения из этого класса для сравнения элементов.
Сначала опишем интерфейс Cmp, который определяет единственную функцию cmp, сравнивающую два значения типа Object:
interface Cmp {
int cmp(0bject x, Object y);
}
Теперь мы можем написать функции сравнения, которые реализуют этот интерфейс; например, следующий класс определяет функцию, сравнивающую объекты типа Integer:
;
А эта функция сравнивает объекты типа String:
Данным способом можно сортировать только типы, наследуемые от класса Object; подобный механизм нельзя применять для базовых типов, таких как int или double. Поэтому мы сортируем элементы типа Integer, а не int.
С этими компонентами мы теперь можем перенести функцию быстрой сортировки из языка С в Java и вызывать в ней функцию сравнения из объекта Cmp, переданного параметром.