Топ 10 алгоритмов сотрировки в Java

Алгоритмы сортировки это алгоритмы которые вставляют элементы в список в определенном порядке. Наиболее используемые это числовая и лексикографическая сортировки. Класс Arrays в Java Collections содержит перегруженный метод sort() для сортировки примитивных типов данных и объектов.

Аналогично мы можем отсортировать коллекцию используя метод Collections.sort(). Но если нам надо отсортировать данные без использования библиотечных методов, мы можем использовать популярные алгоритмы сортировки реализованные на Java.

Простая сортировка

Сортировка выбором представляет собой механизм сортировки, который начинается с поиска наименьшего элемента в массиве и размешение его первым. Затем находится второй наименьший элемент и размещается вторым, и так до тех пор пока весь массив не отсортируется.

Вывод: 1 2 3 4 5 6 7 8 9 10

Алгоритм сортировки вставкой просматривает данные в виде двух половинок. Левая половина отсортированных элементов, правая которые нужно отсортировать. В каждой итерации, один элемент из правой половины берется и добавляется в левую половину так, что левая половина по-прежнему остается отсортированной. Сортировка вставкой сортирует за время О(n²)

Ввод: int[] elements = < 3, 2, 5, 7, 1,9>;

Вывод: 1 2 3 5 7 9

Но что если нам надо отсортировать массив строк? Мы можем изменить логику сравнения в цикле и использовать метод compareTo(). Этот метод может принимать любой массив элементов реализующих интерфейс Comparable.

Вывод: Com, Dot, Http, Java, Top, Tutorial

Эффективная сортировка

Пирамидальная сортировка является методом сортировки, который интерпретирует элементы в массиве, как почти полное бинарное дерево. Она берет элементы массива и вставляет их в пирамиду. После построения пирамиды, из нее по очереди удаляются наибольшие элементы и вставляются в конец массива, где и находятся в отсортированном виде. Общее время сортировки расчитывается по O(N logN) для N элементов.

Вывод: 2 12 15 16 23 27 34 45 53 56 78 91

Сортировка слияние один из наиболее популярных алгоритмов в Java так как использует наименьшее количество сравнений. Сортировка слиянием используется в стандартных Java библиотеках для сортировки generic. Идеей сортировки слиянием является то, что происходит слияние двух отсортированных списков. Сортировка слиянием занимает O(nlogn).

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

Сортировка слиянием в Java:

Вывод: 1 2 3 4 5 6 7 8 9 10

Быстрая сортировка это алгоритм быстрой сортировки. Его среднее время O(N logN), наихудшее O(N²).

Вывод: 1 2 3 4 5 6 7 8 9 10

Пузырьковая сортировка и варианты

Пузырьковая сортировка следует простой логике. Она сравнивает соседние элементы и меняет местами если они не отсортированы. Пузырьковая сортировка названа таким образом потому, что в этом способе сортировки, меньшие элементы постепенно всплывают в верхнюю часть списка. Пузырьковая сортировка имеет среднее и наихудшее время равное О(n²), где n количество элементов которое нужно отсортировать.

Вывод: 1 2 3 4 5 6 7 8 9 10

Дональд Шелл опубликовал первую версию этой сортировки, отсюда и название. Эта сортировка является обобщением сортировки вставкой, что позволяет осуществлять обмен элеметов, которые находятся далеко друг от друга. Она начинается, сравнивая элементы, которые далеки друг от друга, и постепенно уменьшает растояние между сравниваемыми элементами. Время работы меняется в зависимости от последовательности промежутков используемых для сортировки элементов.

Вывод: 1 2 3 4 5 6 7 8 9 10

Распределенная сортировка

Алгоритм блочной сортировки распределяет элементы массива в некоторое число блоков. Это сортировка без сравнения.

Работает блочная сортировка следующим образом:

• создается массив пустых инициализированных блоков;
• программа обходит оригинальный массив и вставляет каждый элемент в блок;
• каждый блок имеющий по крайней мере один элемент сортируется;
• все элементы вставляются назад в оригинальный массив.

Вывод: 1 2 3 4 5 6 7 8 9 10

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

Есть два основных типа поразрядной сортировки:

• LSD поразрядная сортировка — сортировка начинается с младшего разряда (LSD), и продолжается до наиболее значимой цифры (MSD);
• MSD поразрядная сортировка — сортировка начинается с наибольшего разряда (MSD), и продолжается до наименьшей значимой цифры (LSD).

Вывод: 2 3 23 24 44 45 66 75 90 170 232 234 802

Алгоритм перебора элементов, вычисляющий количество раз когда каждый ключ встречается в пределах массива. Тогда для каждого ключа, определяется начальная позиция в выходном массиве элементов, имеющем этот ключ. Время работы линейно по количеству элементов, зависит от разницы между максимальным и минимальным значениями ключа.