Ветераны программирования иногда вспоминают о том, как им приходилось использовать перфокарты и как вручную программировать алгоритмы сортировки. В наши дни, конечно, алгоритмы сортировки являются частью стандартной библиотеки в большинстве языков программирования, и язык программирования Java — не исключение.
Метод sort() класса Collections сортирует коллекцию, реализующую интерфейс List.
|
1 2 3 |
List staff = new LinkedList(); // наполнение коллекции . . .; Collections.sort(staff); |
Этот метод предполагает, что элементы списка реализуют интерфейс Comparable.
Если вы хотите сортировать каким-то другим способом, вы можете передать объект Comparator в качестве второго параметра конструктора. Вот так можно отсортировать список элементов:
|
1 2 3 4 5 6 7 8 |
Comparator itemComparator = new Comparator() { public int compare(Item a, Item b) { return a.partNumber - b.partNumber; } } Collections.sort(items, itemComparator); |
Если вы захотите отсортировать список в порядке убывания, используйте удобный статический метод Collections.reserveSort(). Он вернет компаратор, возвращающий b.compareTo(a). Например, показанный ниже вызов сортирует элементы списка staff в обратном порядке — согласно упорядочиванию, заданному методом compareTo() типа элементов.
|
1 |
Collections.sort(staff, Collections.reserveOrder()) |
Аналогично, следующий вызов обращает порядок, задаваемый itemComparator.
|
1 |
Collections.sort(items, Collections.reserveOrder(itemComparator)) |
Вас может заинтересовать каким образом метод sort() сортирует список. Обычно, если посмотреть на алгоритм сортировки в книге по алгоритмам, он представляется для массивов с использованием произвольного доступа к элементам. Однако произвольный доступ к элементам списка неэффективен.
Вы можете эффективно сортировать списки, использую форму сортировки слиянием. Однако реализация на языке Java не делает этого. Она просто сбрасывает все элементы в массив, сортирует этот массив, применяя другой вариант сортировки слиянием, и затем копирует отсортированную последовательность обратно в список.
Алгоритм сортировки слиянием, используемый в библиотеке коллекций, немного медленнее быстрой сортировки(quick sort) — традиционного выбора для алгоритмов сортировки общего назначения. Однако он имеет одно важное преимущество: он стабилен, то есть не меняет местами эквивалентные элементы.
Зачем беспокоиться о порядке эквивалентных элементов? Рассмотрим распространенный сценарий. Предположим, что у вас есть список сотрудников, который вы уже отсортировали по именам. Теперь вы сортируете по зарплате. Что случится с сотрудниками с одинаковой зарплатой? При стабильной сортировке порядок по именам сохраняется. Другими словами, в результате получим список, отсортированный сначала по зарплате, потом по имени.
Avi1.ru — спешите, чтобы заказать рекламу YouTube с максимально выгодными предложениями уже сейчас! При этом Вы получаете все, что нужно для грамотного продвижения в сети: подписчиков, лайки и просмотры в пакетных услугах. К тому же сервис предоставляет множество бонусов и скидок для покупателей.
Поскольку коллекциями не обязательно реализовывать все «необязательные» методы, все методы, принимающие параметры-коллекции, должны указывать, когда передавать коллекцию алгоритму безопасно. Например, очевидно, что вы не захотите передать список unmodifiableList алгоритму сортировки. Какого рода списки вы можете передавать? Согласно документации, список должен быть модифицируемым, но не должен быть изменяемым в размере.
Термины определяются следующим образом:
- Список является модифицируемым, если он поддерживает метод set().
- Список является изменяемым в размере, если он поддерживает методы add() и remove().
Класс Collections имеет алгоритм shuffle, который выполняет противоположную сортировке задачу: случайным образом изменяет порядок элементов в списке.
Например:
|
1 2 |
ArrayList cards = ...; Collections.shuffle(cards); |
Если вы примените список, который не реализует интерфейс RandomAccess, то метод shuffle скопирует все элементы в массив, перетасует этот массив, после чего скопирует перетасованные элементы обратно в список.
Программа которая приведена ниже заполняет массив-список 49 объектами Integer, содержащими числа от 1 до 49. Затем она случайно тасует их в списке и выбирает первые 6 значений из перетасованного списка. И, наконец, она сортирует выбранные значения и печатает их.
Вот собственно программа которая демонстрирует алгоритмы случайного тасования и сортировки:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
import java.util.*; public class ShuffleTest { public static void main(String[] args) { List numbers = new ArrayList(); for(int i=1; i<=49; i++) numbers.add(i); Collections.shuffle(numbers); List winningCombination = numbers.subList(0, 6); Collections.sort(winningCombination); System.out.println(winningCombination); } } |
Видео по теме:
