Java: сортировка ArrayList на месте

Question

В стандартной библиотеке Java существует ли метод, позволяющий сортировать ArrayList на месте, то есть используя O(1) дополнительное хранилище?

Collections.sort(List<T>) не выполняет это требование, поскольку он

сбрасывает указанный список в массив, сортирует массив и итерацию по списку перезапуске каждый элемент из соответствующей позиции в массиве.

Если в стандартной библиотеке нет ничего, какие сторонние библиотеки могут быть использованы для этого?

Answer 1

Вы можете извлечь базовый массив (например, отражение) и выполнить массив Arrays.sort (array, 0, list.size()) на нем.

Java 7 не копирует массив в массиве Arrays.sort() перед сортировкой массива. В Java 6 это означает, что Collections.sort() в Java 6 фактически копирует базовый массив TWICE для выполнения сортировки.

Answer 2

Просто, нет. Collections.sort() был создан для сортировки, кажется, что вы должны реализовать свои собственные. Для списков я использовал бы Bubblesort, потому что он просто обменивает два соседних элемента, что можно сделать очень просто без изменения Ковши.

Answer 3

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

Если вы действительно обеспокоены сортировкой на месте, вам придется развернуть свою собственную функцию. Это не стоит вашего времени, если только ваш список очень длинный.

Arrays.sort(Object[]) делает то же самое, и слиянием вызывается внутренне Collections.sort() (по крайней мере, в OpenJDK)