Какие разные алгоритмы сортировки доступны в Java 6?

Question

Существует несколько алгоритмов сортировки, таких как сортировка вставкой, сортировка выбора, сортировка по пузырькам и т. Д., Которые часто обсуждаются в учебниках по информатике.Имеется ли массив целых чисел или объектов, есть ли встроенный API языка Java 6, который позволяет мне применять специальный алгоритм сортировки для сортировки массива, а не заново изобретать эти колеса?Если они не встроены в Java 6, существуют ли библиотеки с открытым исходным кодом, которые поддерживают эту функциональность, и чем они являются?

Answer 1

Методы Arrays.sort() используют быструю сортировку во всех массивах примитивного типа.

Алгоритм сортировки представляет собой настроенную быструю сортировку, адаптированную Джоном Л. Бентли и М.Дуглас Макилрой "Инженерные функции сортировки", Software-Practice and Experience, Vol.23 (11) P. 1249-1265 (ноябрь 1993).Этот алгоритм обеспечивает производительность n * log (n) для многих наборов данных, которые приводят к снижению быстродействия других быстрых сортировок до квадратичной производительности.

В методе Collections.sort() используется сортировка слиянием.Эта сортировка также используется в Arrays.sort(Object[]) и Arrays.sort(T[], Comparator<? super T>).

Алгоритм сортировки представляет собой модифицированную сортировку слиянием (в которой объединение опускается, если самый высокий элемент в младшемподсписок меньше самого низкого элемента в верхнем подсписке).Этот алгоритм предлагает гарантированную производительность n log (n).Эта реализация сбрасывает указанный список в массив, сортирует массив и выполняет итерацию по списку, сбрасывая каждый элемент с соответствующей позиции в массиве.Это позволяет избежать производительности n2 log (n), которая может возникнуть в результате попытки отсортировать связанный список на месте.

Answer 2

Arrays.sort(int[] a) использует настроенную быструю сортировку.

Arrays.sort[Object[] a) использует измененную сортировку слиянием.

Answer 3

Как правило, вы не можете выбирать (в любом случае, со встроенной сортировкой). Класс Collections предоставляет метод sort, который должен быть достаточно эффективным для большинства нужд.