Основы сортировки

Сортировка — это порядок по правилу

Отсортировать набор — значит расположить элементы так, чтобы каждая соседняя пара соответствовала выбранному правилу. Для чисел это часто порядок по возрастанию, но само правило может быть любым: по убыванию, по длине строки, по одному из полей объекта и так далее.

int[] values = {8, 3, 6, 1};
Arrays.sort(values);

// 1, 3, 6, 8

Если алгоритм сортирует числа по возрастанию, после его работы для каждого допустимого i должно выполняться values[i] <= values[i + 1]. Это простая формулировка результата, но способы получить его могут сильно отличаться.

Что сравнивать у алгоритмов сортировки

Зная Big O, можно сравнивать алгоритмы не только по тому, «работают» они или нет. Для сортировок обычно важны несколько характеристик: временная сложность, дополнительная память, поведение на почти отсортированных данных и необходимость менять исходный массив.

Например, один алгоритм может быть O(n²), но почти не использовать дополнительную память, а другой — работать за O(n log n), зато создавать вспомогательный массив. Универсально лучшего варианта для всех условий нет.

Сравнения и обмены

Большинство классических сортировок над произвольными значениями строятся вокруг двух действий: сравнить элементы и при необходимости изменить их положение. Разница между алгоритмами — в том, какие элементы они сравнивают и как постепенно приводят весь массив к порядку.