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

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

Использование метода 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;
		}

22 комментария

maks1m
Я пока что не сильно силен в java.
Подскажите зачем вот эта конструкция
{
        public int compare(ObjectName o1, ObjectName o2) {
                return o1.toString().compareTo(o2.toString());
        }

добавлена после вызова метода?
eGarmin
  • eGarmin
  • +1
  • Комментарий отредактирован 2014-06-15 11:06:05 пользователем eGarmin
Дело в том, что она добавлена не после вызова метода, а прямо в его вызов.
Смотрите внимательно где закрываются круглые скобки вызова и где стоит точка с запятой,
обозначающая, что вызов закончен.
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 для сортировки
по убыванию.
maks1m
Спасибо, понял про объект который создается прямо на месте.
Но ведь если не передавать в sort этот объект Comparator то коллекция тоже отсортируется!?
То есть этот Comparator используется только для задания направления сортировки?
eGarmin
По большому счету да, если не указать компаратор, то сортировка будет идти
с компаратором по умолчанию. Для строк — это по алфавиту, а для чисел — по возрастанию.
HedgehogInTheMist
По поводу последнего абзаца «Плохой подход к задаче сортировки». В принципе я согласен, но полагаю, что знать как руками отсортировать все же наверное необходимо. И подскажите, кто более опытный, спрашивают ли на собеседованиях реализацию сортировки, ну например реализовать тут же на листике?
Diana
вполне могут спросить
Soup
  • Soup
  • 0
Подскажите какой вид сортировки реализован в этом стандартном пакете? Быстрая или блочная или другой вариант?
Вы написали, что эффективность log(n) — что имеется ввиду: сложность алгоритма или дополнительная память? Все известные мне сортировки имеют сложность алгоритма как минимум n, может вы хотели сказать n*log(n)?
Заранее спасибо
EvIv
насколько я знаю, в Java реализованы в качестве стандартных сортировки: MergeSort для коллекций объектов и слегка модифицированный (3-way partioning) QuickSort для коллекций примитивов.
QuickSort немного быстрее, но MergeSort стабильный, что может быть важно для объектов, которые могут сортировать последовательно с по разным полям.
sbjng
  • sbjng
  • 0
  • Комментарий отредактирован 2016-02-11 22:50:43 пользователем sbjng
Для русского языка такая конструкция не совсем корректна
<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>
Такая конструкция без проблем обрабатывает эти случаи, хотя производительность оставляет желать лучшего)
valera7979
  • valera7979
  • 0
  • Комментарий отредактирован 2016-04-04 19:30:29 пользователем valera7979
Плохой подход к задаче сортировки

До сих пор можно встретить примеры, когда программисты самостоятельно описывают алгоритмы сортировки.
Да, но все таки часто приходится писать самому. Метод 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. А нужно в возрастающем порядке. Так что ручками, ручками… :)

з.ы. если в коллекции числовые значения то отсортирует как надо. т.е. можно выделить число из строки и уже потом сортировать. Может есть какой-то метод который все это сразу делает
Bushrut
Потому-что он сортирует используя unicode. После преобразования 31 раньше 4.
IgorBrest
Не могу согласиться, метод sort все хорошо сортирует, нужно только показать, что ты от него ждешь, с помощью comparator.
Нет, ну можно, конечно, и ручками, например реализовать quick sort для своей коллекции, в таком случае скорость сортировки можно немного увеличить…
EvIv
Нормально он сортирует числа. Если дать ему числа.
В описанном же случае вы дали ему строки, и сортирует он строки — по «алфавиту».
Для такой задачи не нужно изобретать свою сортировку — нужно просто «распилить» имена файлов на собственно имя и число (или просто выделить этот номер из имени), которое перевести в int. Из этой пары значений создать объект с компаратором по интовому полю и отсортировать коллекцию (или) массив таких объектов стандартным методом по указанному компаратору.
Santegra
Твой распил тоже требует времени, соответственно производительность пострадает.
Evleaps
Верно сказал 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_pi
Не могу разобраться, а зачем в конце каждой строчки a и b кавычки — ""?
kuznechic95
Можете привести пример сортировки чисел по спаданию с помощью 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;
            }
        }

IgorBrest
просто у тебя ошибка в синтаксисе, скобочки для конструктора забыл:
new Comparator<ObjectName>()
kuznechic95

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

По этой же причине не работает Collections.reverseOrder(array)?
kirjust
еще, по моему, важно указать, что в методе sort используются алгоритмы, эффективнее qsort
вот об эффективности алгоритмов сортировки:
habrahabr.ru/post/204600/
Vasilii
А как обрабатывать тот кейс, например, в Collections.sort, если в массиве со значениями случайно окажется null?
fatfaggy
нуу, как вариант — вот так:

new Comparator() {
    public int compare(Object x, Object y) {
        if (x == null) return Integer.MIN_VALUE;    // возвращаем заведомо маленькое число чтоб значения с null всплывали вверх при сортировке
        ...    // код компаратора если не null
    }
}
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.