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

#java #sorting #arraylist

#java #сортировка #список массивов

Вопрос:

Существует ли в стандартной библиотеке Java метод, который позволил бы сортировать ArrayList на месте, т. Е. Использовать O(1) дополнительное хранилище?

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

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

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

Ответ №1:

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

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

1. Единственное, что это берет копию массива и поэтому использует O (n) дополнительного хранилища в соответствии с Collections.sort.

2. В Java 7 он не принимает копию. Я не проверял Java 6.

3. Интересно. На самом деле я очень удивлен, что они изменили поведение, чтобы вернуть базовый массив; могу себе представить, что это вызовет множество мелких ошибок у людей, обновляющихся с Java 6.

4. Arrays.sort() ничего не возвращает. Вопрос в том, копирует ли он массив перед его сортировкой.

5. В Java 8 Collections.sort вызывает sort список, так что это зависит от реализации списка. ArrayList вызывает Arrays.sort его элемент array, так что он все еще на месте.

Ответ №2:

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

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

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

Ответ №3:

Начиная с Java 8 List , интерфейс имеет void sort(Comparator<? super E> c) API по умолчанию, с помощью которого вы можете сортировать экземпляр на месте.

Список должен быть изменяемым, итерируемым, а его элементы должны быть сопоставимы друг с другом.