User eGarmin
eGarmin
41 уровень

Как правильно делать сортировку в Java

Статья из группы Архив info.javarush.ru
Анализируя исходные коды многих opensource Java-проектов, я обнаружил, что большинство разработчиков осуществляют сортировку всего двумя разными способами. Один из них основан на применении метода sort() классов Collections или Arrays, а другой на использовании самосортирующихся структур данных, таких как TreeMap и TreeSet. Как правильно делать сортировку в Java - 1

Использование метода sort()

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

// Collections.sort(…)
List<ObjectName> list = new ArrayList<ObjectName>();
Collections.sort(list, new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});
Если требуется отсортировать массив, используйте метод Arrays.sort().

// Arrays.sort(…)
ObjectName[] arr = new ObjectName[10];
Arrays.sort(arr, new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});
Метод sort() очень удобен, когда коллекция или массив уже заполнены значениями.

Применение самосортирующихся структур данных

Если нужно отсортировать список (List) или множество (Set), используйте структуру TreeSet для сортировки.

// TreeSet
Set<ObjectName> sortedSet = new TreeSet<ObjectName>(new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});
sortedSet.addAll(unsortedSet);
Если вам требуется отсортировать словарь (Map), используйте структуру TreeMap для сортировки. TreeMap сортируется по ключу (key).

// TreeMap – использующий String ключи и компаратор (Comparator) CASE_INSENSITIVE_ORDER,
// упорядочивающий строки (String) методом compareToIgnoreCase
Map<String, Integer> sortedMap = new TreeMap<String, Integer>(String.CASE_INSENSITIVE_ORDER);
sortedMap.putAll(unsortedMap);

//TreeMap – общий случай, компаратор указывается вручную
Map<ObjectName, String> sortedMap = new TreeMap<ObjectName, String>(new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});
sortedMap.putAll(unsortedMap);
Вышеописанный подход очень полезен в тех случаях, если вам нужно проводить большое количество операций поиска элементов в коллекции. Самосортирующиеся структуры данных имеют эффективность O(log(n)), что лучше, чем O(n). Это означает, что при удвоении количества данных в коллекции время поиска не удваивается, а увеличивается на постоянную величину (прим. перев.)

Плохой подход к задаче сортировки

До сих пор можно встретить примеры, когда программисты самостоятельно описывают алгоритмы сортировки. Рассмотрим код сортировки, представленный ниже (сортировка double-массива по возрастанию (прим. перев.)). Этот код не только не эффективен, но и не читабелен. И таких примеров много.

double t;
for (int i = 0; i < N; i++)
	for (int j = i + 1; j < N; j++)
		if (r[j] < r[i]) {
			t = r[i];
			r[i] = r[j];
			r[j] = t;
		}
Комментарии (48)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ СДЕЛАТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
ERGAN Уровень 22
29 ноября 2020
Прекрасный пример того, как можно было написать все и ничего в одной статье.
Николай Уровень 23, Всеволожск, Россия
17 июля 2020
Статья на тему: "Глядите, лохи, как я крут!"
Евгений Уровень 37, Коряжма, Россия
1 июля 2020
То чувство, когда "Плохой подход к задаче сортировки" из вашей статьи, гораздо понятнее всего остального 😳
Виталий Уровень 9, Ставрополь, Россия
4 марта 2020
Ребята!!!!! Объясните логику сортировки пожалуйста, я не догоняю вообще в чем прикол. что с чего начать, куда смотреть. У меня задание типа электронной книги. 1.если ввожу номер телефона , просит ввести имя 2.если ввожу имя просит ввести номер телефона 3. если ввожу существующее имя или существующий номер телефона, программа выдает полностью контакт. 4. при команде LIST должен распечататься весть список контактов 5. при распечатке все контактов , имена должны быть отсортированы в алфавитном порядке Сделал все пункты кроме последнего. Использовал коллекцию TreeMap, но дело в том что номера телефонов у меня ключи, а имена это значения. TreeMap в этой беде не поможет. я вообще догнать не могу как мне отсортировать значения в MAP.
Kazantip Уровень 32
11 февраля 2020
Вот нормальная статья с примерами выполнения сортировки: https://hr-vector.com/java/sortirovka-arraylist
Maksim Demin Уровень 0
11 января 2020
Люди добрые! Помогите отсортировать коллекцию (например) TreeMap<String, String> map map.put("1", "Строка1"); map.put("2", "Строка2"); map.put("4", "Строка4"); map.put("10", "Строка10"); map.put("11", "Строка11"); map.put("15", "Строка15"); Чтобы сортировка при выводе была ни как у меня сейчас 1 строка 1 10 строка 10 11 строка 11 15 строка 15 2 строка 2 4 строка 4 надо чтобы цифры были по порядку
Ирина Уровень 8, Москва, Россия
29 ноября 2019
Странно, что при написании статьи автор не указал, что выводится на экран исходя из его кода. Я впервые сталкиваюсь сортировками и совсем не понимаю, как сортируют описанные им методы, по какому принципу? (больше-меньше, по алфавиту или как?). Ничего не понятно.
Александр Уровень 13, Москва, Россия
6 мая 2019
Как вообще узнать, что писать в импорте, чтобы подключить коллекции? ни черта нигде нет об этом, а без импорта код не работает. черт возьми, где его взять? почему бы не сделать хоть какой то навигатор по классам? p.s. я на 7-м уровне и у меня нет возможности глянуть в шапку заготовки уроков последующих уровней
Andrey Pushkarev Уровень 35, Россия
2 марта 2019
Если нужно отсортировать список (List) или множество (Set), используйте структуру TreeSet для сортировки может я чего не уловил... каким образом предлагается отсортировать список, запихав его в Treeset?
Александр Моцар Уровень 28, Минск, Беларусь
31 октября 2018
последняя ручная сортировка - сортировка выбором, это действительно самый медленный вариант который есть. НО стоит отметить что сортировки методом Arrays.sort и Collections.sort реализованы методом "Quick sort" и в самом неблагоприятном случае время для такого вида сортировки ничем не отличается от приведенной выше самописной сортировки. Хотя бесспорно Arrays.sort() лучше использовать чем то что предлагают в конце. К чему вообще стал писать этот коммент: две недели назад был на двух собеседованиях и на каждом из них, что было достаточно удивительно, меня попросили написать код сортировки ПРИЧЕМ В РУЧНУЮ. Ответ типа сортируем методом sort() не принимался. На втором собеседовании интервьюера вполне устроил код самой простой пузырьковой сортировки, приведенный выше вариант тоже вполне бы сгодился. А вот на первом, такой простой вариант уже не прокатил) Также совершенно недавно знакомый делал тестовое задание на java junior в котором одной из задач было объединить два не отсортированных массива чисел в один отсортированный) Естественно предполагалось что человек не просто два раза вызовет метод sort(), а как минимум сделает это но в двух разных потоках. В общем к моему удивлению, такие вопросы на интервью любят. Поэтому лучше кроме стандартных методов потратить полчаса времени и реализовать для себя пару вариантов сортировки вручную, желательно с применением многопоточности. Например пузырьковую ну и сортировку слиянием, алгоритмы достаточно простые. Чтоб на собеседовании не вспоминать лихорадочно "как жеж там оно это пишется, ведь просто ж все)", а взять и написать за минуту, да еще и О-нотацию указать для каждого варианта.