Быстрая сортировка на языке Java
Наиболее существенное изменение – это использование индексов left и right, поскольку в Java нет указателей на массивы.
Quicksort.sort использует cmp для сравнения двух объектов, как и раньше, вызывает swap для их обмена.
Генерация случайного номера происходит в функции rand, которая а возвращает случайное число в диапазоне с left по right включительно:
Мы вычисляем абсолютное значение (используя функцию Math.abs), поскольку в Java генератор случайных чисел возвращает как положительные, так и отрицательные значения.
Функции sort, swap и rand, а также объект-генератор случайных чисел rgen являются членами класса Quicksort.
Наконец мы готовы написать вызов Quicksort.sort для сортировки массива типа String:
Так вызывается sort с объектом сравнения строк, созданным для этой цели.
Упражнение 2.2
Наша реализация быстрой сортировки в Java делает несколько преобразований типов, сначала переводя исходные данные из их первоначального типа (вроде Integer) в Object, а затем обратно. Поэкспериментируйте с версией Quicksort.sort, которая использует конкретный тип при сортировке, и попробуйте вычислить, какие потери производительности вызываются преобразованием типов.