Сортировка и перетасовка Java

Сортировка и перетасовка JavaВетераны программирования иногда вспоминают о том, как им приходилось использовать перфокарты и как вручную программировать алгоритмы сортировки. В наши дни, конечно, алгоритмы сортировки являются частью стандартной библиотеки в большинстве языков программирования, и язык программирования Java — не исключение.

Метод sort() класса Collections сортирует коллекцию, реализующую интерфейс List.

Этот метод предполагает, что элементы списка реализуют интерфейс Comparable.

Если вы хотите сортировать каким-то другим способом, вы можете передать объект Comparator в качестве второго параметра конструктора. Вот так можно отсортировать список элементов:

Если вы захотите отсортировать список в порядке убывания, используйте удобный статический метод Collections.reserveSort(). Он вернет компаратор, возвращающий b.compareTo(a). Например, показанный ниже вызов сортирует элементы списка staff в обратном порядке — согласно упорядочиванию, заданному методом compareTo() типа элементов.

Аналогично, следующий вызов обращает порядок, задаваемый itemComparator.

Вас может заинтересовать каким образом метод sort() сортирует список. Обычно, если посмотреть на алгоритм сортировки в книге по алгоритмам, он представляется для массивов с использованием произвольного доступа к элементам. Однако произвольный доступ к элементам списка неэффективен.

Вы можете эффективно сортировать списки, использую форму сортировки слиянием. Однако реализация на языке Java не делает этого. Она просто сбрасывает все элементы в массив, сортирует этот массив, применяя другой вариант сортировки слиянием, и затем копирует отсортированную последовательность обратно в список.

Алгоритм сортировки слиянием, используемый в библиотеке коллекций, немного медленнее быстрой сортировки(quick sort) — традиционного выбора для алгоритмов сортировки общего назначения. Однако он имеет одно важное преимущество: он стабилен, то есть не меняет местами эквивалентные элементы.

Зачем беспокоиться о порядке эквивалентных элементов? Рассмотрим распространенный сценарий. Предположим, что у вас есть список сотрудников, который вы уже отсортировали по именам. Теперь вы сортируете по зарплате. Что случится с сотрудниками с одинаковой зарплатой? При стабильной сортировке порядок по именам сохраняется. Другими словами, в результате получим список, отсортированный сначала по зарплате, потом по имени.

Поскольку коллекциями не обязательно реализовывать все «необязательные» методы, все методы, принимающие параметры-коллекции, должны указывать, когда передавать коллекцию алгоритму безопасно. Например, очевидно, что вы не захотите передать список unmodifiableList алгоритму сортировки. Какого рода списки вы можете передавать? Согласно документации, список должен быть модифицируемым, но не должен быть изменяемым в размере.

Термины определяются следующим образом:

  • Список является модифицируемым, если он поддерживает метод set().
  • Список является изменяемым в размере, если он поддерживает методы add() и remove().

Класс Collections имеет алгоритм shuffle, который выполняет противоположную сортировке задачу: случайным образом изменяет порядок элементов в списке.

Например:

Если вы примените список, который не реализует интерфейс RandomAccess, то метод shuffle скопирует все элементы в массив, перетасует этот массив, после чего скопирует перетасованные элементы обратно в список.

Программа которая приведена ниже заполняет массив-список 49 объектами Integer, содержащими числа от 1 до 49. Затем она случайно тасует их в списке и выбирает первые 6 значений из перетасованного списка. И, наконец, она сортирует выбранные значения и печатает их.

Вот собственно программа которая демонстрирует алгоритмы случайного тасования и сортировки:

Видео по теме:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *