eGarmin
41 уровень

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

Пост из группы Архив info.javarush.ru
3745 участников
Анализируя исходные коды многих opensource Java-проектов, я обнаружил, что большинство разработчиков осуществляют сортировку всего двумя разными способами. Один из них основан на применении метода sort() классов Collections или Arrays, а другой на использовании самосортирующихся структур данных, таких как TreeMap и TreeSet.
Использование метода sort()
Если нужно отсортировать коллекцию, то применяйте метод Collections.sort(). // Collections.sort(…) List list = new ArrayList(); Collections.sort(list, new Comparator() { 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() { public int compare(ObjectName o1, ObjectName o2) { return o1.toString().compareTo(o2.toString()); } }); Метод sort() очень удобен, когда коллекция или массив уже заполнены значениями.
Применение самосортирующихся структур данных
Если нужно отсортировать список (List) или множество (Set), используйте структуру TreeSet для сортировки. // TreeSet Set sortedSet = new TreeSet(new Comparator() { 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 sortedMap = new TreeMap(String.CASE_INSENSITIVE_ORDER); sortedMap.putAll(unsortedMap); //TreeMap – общий случай, компаратор указывается вручную Map sortedMap = new TreeMap(new Comparator() { 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; }
Комментарии (26)
  • популярные
  • новые
  • старые
Для того, что бы оставить комментарий вы должны авторизоваться
Rihard198525 уровень
29 июля, 12:55
Я из этой статьи понял одно, напрягай мозги меньше придумывая велосипед который уже есть и пользуйся им.
Geolimber13 уровень
27 января, 03:38
Я бы добавил ещё один полезный пример, который вычитал из Философии Java. Обратная сортировка.
Arrays.sort(sa, Collections.reverseOrder());
Israfil9 уровень
вчера, 12:45
Если бы ты знал как сейчас помог мне DD
Vasilii11 уровень, Санкт-Петербург
17 ноября 2017, 21:36
А как обрабатывать тот кейс, например, в Collections.sort, если в массиве со значениями случайно окажется null?
fatfaggy26 уровень, Киев
17 ноября 2017, 22:19
нуу, как вариант — вот так:

new Comparator() {
    public int compare(Object x, Object y) {
        if (x == null) return Integer.MIN_VALUE;    // возвращаем заведомо маленькое число чтоб значения с null всплывали вверх при сортировке
        ...    // код компаратора если не null
    }
}
kirjust30 уровень
16 сентября 2016, 13:31
еще, по моему, важно указать, что в методе sort используются алгоритмы, эффективнее qsort
вот об эффективности алгоритмов сортировки:
habrahabr.ru/post/204600/
kuznechic9533 уровень, Киев
29 июля 2016, 16:15
Можете привести пример сортировки чисел по спаданию с помощью Comparator? Очень хочется делать это эффективно, но не получается корректно использовать…
// 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());
        }
});

После прочтения документации вроде стало ясно, НО! компилятор ругается «Cannot resolve symbol x». Тоже самое с o1, o2. И подчеркивает еще много всего…
Также я нашел решение через Collections.reverseOrder(array). Но тоже ругается. Требует Comparator. А как им пользоваться примеров почти нет…
Arrays.sort(array, new Comparator<Integer> {
            public int compare(Integer x, Integer y)
            {
                return y - x;
            }
        }

IgorBrest33 уровень
29 июля 2016, 16:47
просто у тебя ошибка в синтаксисе, скобочки для конструктора забыл:
new Comparator<ObjectName>()
kuznechic9533 уровень, Киев
29 июля 2016, 21:11

Спасибо! Но теперь надо вручную привести int[] to Integer[]:
stackoverflow.com/questions/880581/how-to-convert-int-to-integer-in-java

По этой же причине не работает Collections.reverseOrder(array)?
valera797931 уровень, Харьков
4 апреля 2016, 19:30
Плохой подход к задаче сортировки

До сих пор можно встретить примеры, когда программисты самостоятельно описывают алгоритмы сортировки.
Да, но все таки часто приходится писать самому. Метод Collections.sort() не очень хорошо сортирует числа.
Пример: В коллекцию в произвольном порядке вносились имена файлов (это одна из задач на джавараш)
lion.avi.part5
lion.avi.part4
lion.avi.part31
lion.avi.part6

После сортировки Collections.sort(list) отсортированный список будет выглядеть следующим образом:
lion.avi.part31
lion.avi.part4
lion.avi.part5
lion.avi.part6

Т.е. он посчитал что 31 меньше чем 4. А нужно в возрастающем порядке. Так что ручками, ручками… :)

з.ы. если в коллекции числовые значения то отсортирует как надо. т.е. можно выделить число из строки и уже потом сортировать. Может есть какой-то метод который все это сразу делает
Bushrut21 уровень
4 мая 2016, 20:47
Потому-что он сортирует используя unicode. После преобразования 31 раньше 4.
IgorBrest33 уровень
4 мая 2016, 22:27
Не могу согласиться, метод sort все хорошо сортирует, нужно только показать, что ты от него ждешь, с помощью comparator.
Нет, ну можно, конечно, и ручками, например реализовать quick sort для своей коллекции, в таком случае скорость сортировки можно немного увеличить…
EvIv30 уровень
5 мая 2016, 13:05
Нормально он сортирует числа. Если дать ему числа.
В описанном же случае вы дали ему строки, и сортирует он строки — по «алфавиту».
Для такой задачи не нужно изобретать свою сортировку — нужно просто «распилить» имена файлов на собственно имя и число (или просто выделить этот номер из имени), которое перевести в int. Из этой пары значений создать объект с компаратором по интовому полю и отсортировать коллекцию (или) массив таких объектов стандартным методом по указанному компаратору.
Santegra31 уровень, Санкт-Петербург
7 ноября 2016, 21:55
Твой распил тоже требует времени, соответственно производительность пострадает.
Evleaps23 уровень, Нижний Новгород
21 апреля 2017, 16:23
Верно сказал IgorBrest, нужно лишь дать понять, а что именно сортировать!
Вот так все будет работать отлично!:)
Collections.sort(list, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                int a = Integer.parseInt(o1.split("part")[1]+"");
                int b = Integer.parseInt(o2.split("part")[1]+"");
                return a - b;
            }
        });
an_pi22 уровень, Киев
2 мая 2017, 11:37
Не могу разобраться, а зачем в конце каждой строчки a и b кавычки — ""?
sbjng25 уровень
11 февраля 2016, 22:50
Для русского языка такая конструкция не совсем корректна
<code>public int compare(ObjectName o1, ObjectName o2) {
                return o1.toString().compareTo(o2.toString());
        }</code>
Возникают вопросы со словами типа «Ежик», «Йод» и т.д.
<code>Comparator<String> comparator = new Comparator<String>() {
            public int compare(String arg1, String arg2) {
                Collator сollator = Collator.getInstance(new Locale("ru", "RU")); 
                сollator.setStrength(Collator.PRIMARY);
                return сollator.compare(arg1, arg2);
            }
        };</code>
Такая конструкция без проблем обрабатывает эти случаи, хотя производительность оставляет желать лучшего)
Soup25 уровень, Новосибирск
18 января 2016, 09:00
Подскажите какой вид сортировки реализован в этом стандартном пакете? Быстрая или блочная или другой вариант?
Вы написали, что эффективность log(n) — что имеется ввиду: сложность алгоритма или дополнительная память? Все известные мне сортировки имеют сложность алгоритма как минимум n, может вы хотели сказать n*log(n)?
Заранее спасибо
EvIv30 уровень
18 января 2016, 13:00
насколько я знаю, в Java реализованы в качестве стандартных сортировки: MergeSort для коллекций объектов и слегка модифицированный (3-way partioning) QuickSort для коллекций примитивов.
QuickSort немного быстрее, но MergeSort стабильный, что может быть важно для объектов, которые могут сортировать последовательно с по разным полям.
HedgehogInTheMist19 уровень, Минск
20 октября 2015, 23:10
По поводу последнего абзаца «Плохой подход к задаче сортировки». В принципе я согласен, но полагаю, что знать как руками отсортировать все же наверное необходимо. И подскажите, кто более опытный, спрашивают ли на собеседованиях реализацию сортировки, ну например реализовать тут же на листике?
Diana41 уровень
21 октября 2015, 09:39
вполне могут спросить
maks1m25 уровень
15 июня 2014, 03:36
Я пока что не сильно силен в java.
Подскажите зачем вот эта конструкция
{
        public int compare(ObjectName o1, ObjectName o2) {
                return o1.toString().compareTo(o2.toString());
        }

добавлена после вызова метода?
eGarmin41 уровень
15 июня 2014, 11:06
Дело в том, что она добавлена не после вызова метода, а прямо в его вызов.
Смотрите внимательно где закрываются круглые скобки вызова и где стоит точка с запятой,
обозначающая, что вызов закончен.
Collections.sort(list,
        new Comparator<ObjectName>() {
            public int compare(ObjectName o1, ObjectName o2) {
                return o1.toString().compareTo(o2.toString());
            }
        }
);

В этом коде я по другому расставил переносы строк, чтобы Вы могли увидеть, что
сразу после передачи в метод sort() списка list в метод передается второй параметр.
Этот второй параметр — это объект, который создается прямо на месте и объявляется
прямо на месте в фигурных скобках после вызова конструктора
new Comparator<ObjectName>() {...}

В этих скобках написано объявление метода compare(...) объекта компаратора Comparator<...>.

А если Вы имели ввиду, что в этом методе compare(...) написано не понятно чего, то здесь все
просто: мы наши объекты типа ObjectName (o1 и o2) преобразуем в строки — это всегда возможно,
и сравниваем их по алфавиту. Но можно, конечно, написать сравнение двух объектов по любому другому принципу.
Например, если ObjectName — это Integer, то можно написать так
Collections.sort(list,
        new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        }
);

Для сортировки по возрастанию, либо напишите внутри метода compare(...): o2 — o1 для сортировки
по убыванию.
maks1m25 уровень
15 июня 2014, 14:37
Спасибо, понял про объект который создается прямо на месте.
Но ведь если не передавать в sort этот объект Comparator то коллекция тоже отсортируется!?
То есть этот Comparator используется только для задания направления сортировки?
eGarmin41 уровень
15 июня 2014, 16:02
По большому счету да, если не указать компаратор, то сортировка будет идти
с компаратором по умолчанию. Для строк — это по алфавиту, а для чисел — по возрастанию.
Rihard198525 уровень
29 июля, 12:57
а почему объект ведет себя как метод?? то есть он создается и сразу тело появляется как в методе это лямбда выражения типа того?