Сортировка выбором

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

Алгоритм:
1. Начинаем с того, что весь входной массив считается неотсортированным.
2. Перебираем неотсортированную часть массива, чтобы найти минимальный (или максимальный) элемент.
3. Как только минимальный (или максимальный) элемент определен, он заменяется первым элементом в несортированной части.
4. Продолжаем этот процесс, уменьшая размер неотсортированной части на один элемент на каждой итерации, пока весь массив не будет отсортирован.

Сложность алгоритма:
В лучшем случаи: O(n^2)
В cреднем: O(n^2)
В худшем: O(n^2)

Сортировка вставками

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

Алгоритм:
1. Начинаем с первого элемента, который считается отсортированным.
2. Перебираем неотсортированную часть массива, беря по одному элементу за раз и сравниваем его с элементами в отсортированной части массива.
3. Сдвигаем элементы в отсортированной части массива вправо, пока не найдем правильную позицию для текущего элемента.
4. Как только правильная позиция найдена, вставляем текущий элемент в отсортированную часть массива.
5. Продолжаем этот процесс, пока не будет отсортирован весь массив.

Сложность алгоритма:
В лучшем случаи: O(n)
В cреднем: O(n^2)
В худшем: O(n^2)

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

Это алгоритм сортировки по принципу «разделяй и властвуй», который эффективно сортирует элементы, разделяя входные данные на более мелкие подзадачи, сортируя их, а затем объединяя их вместе.

Алгоритм:
1. Рекурсивно разделите входной массив на две половины, пока каждый подмассив не будет содержать только один элемент.
2. Отсортируйте каждый из подмассивов индивидуально.
3. Объедините отсортированные подмассивы вместе, чтобы создать один полностью отсортированный массив. Это достигается путем сравнения элементов двух подмассивов и их объединения в порядке возрастания.
4. Объединенный результат представляет собой отсортированный массив.

Сложность алгоритма:
В лучшем случаи: O(n logn)
В cреднем: O(n logn)
В худшем: O(n logn)

Быстрая сортировка

Это алгоритм сортировки, который эффективно сортирует элементы, разделяя входные данные на более мелкие подзадачи. Он работает путем выбора элемента «pivot» из входных данных и разделения других элементов на два подмассива: элементы меньше, чем «pivot», и элементы, превышающие «pivot». Он рекурсивно сортирует два подмассива.

Алгоритм:
1. Выбор «pivot» из входного массива. (Его выбор может существенно повлиять на производительность алгоритма. Это может быть: первый, последний или случайный элемент).
2. Разделение элементов массива так, чтобы все элементы меньше «pivot» находились перед ним, а все элементы выше «pivot» — после нее.
3. Рекурсивное примените алгоритма быстрой сортировки к подмассиву элементов, меньших опорного, и к подмассиву элементов, превышающих опорный.
4. Продолжайте этот процесс, пока весь массив не будет отсортирован.

Сложность алгоритма:
В лучшем случаи: O(n logn)
В cреднем: O(n logn)
В худшем: O(n^2)

HeapSort

Это алгоритм сортировки на основе сравнения, основанный на структуре данных двоичной кучи. Он используется для эффективной сортировки массива или списка элементов в порядке возрастания или убывания. В отличие от некоторых других алгоритмов сортировки, HeapSort не требует дополнительной памяти для сортировки.

Алгоритм:
1. Преобразование входного массива в максимальную кучу. Максимальная куча — это двоичное дерево, в котором родительский узел больше или равен дочерним узлам.
2. Начиная с конца кучи (последний элемент массива), поменяйте местами корневой элемент (максимальный элемент в куче) с последним элементом.
3. После каждой замены уменьшите размер кучи на единицу и убедитесь, что свойство max-heap сохраняется для остальных элементов.
4. Повторяйте этот процесс, пока весь массив не будет отсортирован.

Сложность алгоритма: O(n logn)

Сортировка подсчётом

Это алгоритм несравнительной сортировки, который работает путем подсчета частоты каждого отдельного элемента во входных данных. Это особенно эффективно при сортировке целых чисел.

Алгоритм:
1. Определение диапазона входных значений и создание вспомогательного массива размером, равным диапазону значений.
2. Подсчет частоты каждого отдельного элемента, сопоставляя его с индексами в массиве подсчета.
3. Создание выходного массива того же размера, что и входной массив.
4. Размещаем элементы в зависимости от вспомогательного массива в новый отсортированный массив.

Cложность: O(N + K), где N — количество элементов во входном массиве, а K — диапазон входных данных.

Поразрядная сортировка

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

Алгоритм:
1. Определить необходимое количество проходов (зависит от количества цифр или символов в максимальном элементе)
2. Создание 10 сегментов (0–9) для каждой позиции цифры (для чисел с основанием 10) или 26 сегментов (A–Z) для каждой позиции символа (для букв верхнего регистра).
3. Распределение элементов по сегментам, начиная с младшей значащей цифры.
4. Сортировка элементов в каждом сегменте, используя стабильный алгоритм сортировки
5. Формирование частично отсортированного массива.
6. Повторение процесса до тех пор пока не получится отсортированный массив.

Сложность:
В лучшем случаи: O(n)
В худшем: O(n*k)

Bucket sort

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

Бакет (bucket — ведро) — это сущность для организации хранения в хранилище.

Шаги сортировки:
1. Создание массива пустых бакетов, каждый из которых представляет определенный диапазон значений.
2. Помещение каждого элемент из входящего массива в соответствующий бакет на основе функции сопоставления.
3. Сортировка каждого бакета индивидуально, используя любой алгоритм сортировки по вашему выбору.
4. Объединение отсортированных бакетов, чтобы получить окончательный отсортированный массив.

Сложность алгоритма: O(n)

Сортировка Шелла

Это алгоритм сортировки, который является расширением алгоритма сортировки вставками. Сортировка Шелла сортирует элементы, удаленные друг от друга на расстояние D, а затем постепенно сокращает разрыв между ними.

Есть огромное количество методов выбора числа D:
1. Самый просто пример это D = n / 2, D2 = D/2 … Dn =1
2. Предложение Хиббарда: проверить на всем N ^i — 1<= N. 
3. Числа Седжвика и много много другого.

Основные шаги в сортировке:
1. Выбрать расстояние D
2. Сформировать подмассивы на основе данного массива и расстояния D.
3. Применяем сортировку вставками к каждому подмассиву
4. Собрать массив
Повторять эти шаги пока массив не будет отсортирован.

Сложность алгоритма:
В лучшем случаи: O(n)
В cреднем: O(n (logn)^2)
В худшем: O(n log^2n)

Tim Sort

Это высокоэффективный и стабильный алгоритм сортировки,, который сочетает в себе элементы сортировки слиянием и сортировки вставками.

Алгоритм:
1. Разделение входного массива на более мелкие сегменты, называемые «runs». Минимальный размер run (minrun) определяется на основе n, исходя из следующих принципов:
- Не должно быть слишком большим, тк в дальнейшем применена сортировка вставками
- Не должно быть слишком маленьким, так как чем меньше run, тем больше итераций слияния придётся выполнить.
- Оптимальная величина n/minrun - степень двойки
2. Сортировка runs с помощью сортировки вставками.
3. Объединение соседних runs с помощью сортировки слияния

Сложность алгоритма:
В лучшем случаи: O(n)
В cреднем: O(n logn)
В худшем: O(n logn)

Блинная сортировка

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

Алгоритм:
Шаг 1. Найдите самый большой блин.
Шаг 2. Переверните стопку, чтобы переместить самый большой «блин» на вершину стека.
Шаг 3. Повторите шаги 2 и 3, но теперь учитывая оставшуюся неотсортированную часть стопки.

Продолжайте пока вся стопка не будет отсортирована: «самый большой блин окажется внизу, а самый маленький — наверху».

Сложность алгоритма:
Лучший случай: O(n) — если массив уже отсортирован, алгоритм может завершиться быстрее, так как будет выполнять меньше переворотов.
Средний случай: O(n²) — алгоритм требует порядка n итераций для нахождения максимального элемента в неотсортированной части массива, и для каждой итерации может потребоваться до n переворотов.
Худший случай: O(n²) — когда элементы находятся в обратном порядке, алгоритму потребуется максимальное количество переворотов для сортировки.

Шейкерная сортировка

Простой алгоритм сортировки, являющийся разновидностью алгоритма пузырьковой сортировки.

Алгоритм:
1. Проход вправо:
- Сравниваем соседние элементы с крайнего левого элемента.
- Если текущий элемент больше следующего элемента, меняем их местами.
- Продолжайте этот процесс, перемещаясь слева направо, пока не дойдете до конца списка. После этого прохода самый большой элемент «всплывает» в конец списка.

2. Проход влево:
- Теперь выполните проход справа налево, сравнивая и меняя местами соседние элементы.
- Если текущий элемент меньше предыдущего, поменяйте их местами.
- Продолжайте этот процесс, перемещаясь справа налево, но остановитесь перед последним отсортированным элементом. После этого прохода наименьший элемент «всплывает» в начало списка.

Сложность:
В лучшем: O(n)
В худшем: O(n^2)

Gnome Sort

Простой алгоритм сортировки. Он называется «Сортировка гномов», потому что напоминает садового гнома, сортирующего ряд цветочных горшков :)

Алгоритм:
Шаг 1: Инициализируйте переменную, называемую «курсор», значением 0 (представляет текущую позицию в списке)
Шаг 2: Сравните элемент в позиции курсора с элементом непосредственно перед ним.
- если элемент в позиции курсора больше или равен элементу перед ним, переместите курсор на одну позицию вправо.
- если элемент в позиции курсора меньше элемента перед ним, поменяйте местами два элемента и переместите курсор на одну позицию влево (возврат).

Сложность:
В лучшем: O(n)
В худшем: O(n^2)

Odd-Even Sort

Простой алгоритм сортировки, предназначенный для параллельной обработки и визуально воспринимаемый как сортировка элементов по «нечетным» и «четным» позициям в списке. По сути, это разновидность пузырьковой сортировки.

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

На нечетном этапе мы выполняем пузырьковую сортировку для элементов с нечетным индексом, а на четном этапе мы выполняем пузырьковую сортировку для элементов с четным индексом.

Сложность:
В лучшем: O(n)
В худшем: O(n^2)

Сортировка расчёской

Простой и эффективный алгоритм сортировки на основе сравнения, который является улучшением алгоритма пузырьковой сортировки.

Алгоритм:
Шаг 1: Инициализируем gap. Обычно он равен длине массива, деленной на 1,3.
Шаг 2: Сравниваем элементы, расположенные на текущем промежутке. Если элементы не в правильном порядке, поменяйте их местами. Продолжайте сравнивать и менять местами элементы с одинаковым зазором по всему массиву.
Шаг 3: Каждый раз по окончанию прохода через весь массив с текущим значением gap, мы уменьшаем его на фиксированный коэффициент 1,3. Повторяем процесс сравнения и замены с новым, меньшим зазором.
Шаг 4: Когда gap = 1, выполните последний проход по массиву. Наш массив отсортирован.

Сложность: O(n*log(n))

Голубиная сортировка

Алгоритм сортировки, который подходит для сортировки списков элементов, в которых количество элементов и количество возможных значений ключа примерно одинаковы.

Работа алгоритма:
Шаг 1: Найдите минимальное (min) и максимальное (max) значения в массиве. Также найдите range как «max-мin+1».
Шаг 2: Создайте массив изначально пустых «ячеек» того же размера, что и диапазон.
Шаг 3: Посетите каждый элемент массива, а затем поместите каждый элемент в свою ячейку. Элемент arr[i] помещается в ячейку с индексом arr[i] – min.
Шаг 4: Запустите цикл по всему массиву ячеек по порядку и поместите элементы из непустых ячеек обратно в исходный массив.

Сложность: O(n+range)

Циклическая сортировка

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

Алгоритм:
Шаг 1: Инициализируйте переменную pos значением 0.
Шаг 2: Для каждого элемента массива сравните его со всеми остальными элементами справа от него. Если есть какие-либо элементы, которые меньше текущего элемента, увеличьте pos.
Шаг 3: Если pos по-прежнему равен 0 после сравнения первого элемента со всеми остальными элементами, перейдите к следующему элементу и повторите шаг 2.
Шаг 4: Как только будет найден меньший элемент, замените текущий элемент первым элементом в его цикле. Затем цикл продолжается до тех пор, пока текущий элемент не вернется в исходное положение.

Повторяйте шаги 3–5, пока не будут завершены все циклы. Теперь массив отсортирован.

Сложность: O(n^2)

Нитевидная сортировка

Рекурсивный алгоритм сортировки, который сортирует элементы списка в порядке возрастания.

Алгоритм:
Пусть input[] — входной список, а output[] — выходной список.

Шаг 1: Создайте еще один пустой список sublist и переместите в него первый элемент input.
Шаг 2: Для каждого элемента x из input проверьте, превышает ли x последний добавленный элемент в список.
- Если да, удалите x из input и добавьте в конец sublist.
- Если нет, игнорируйте x (сохраните его в input)
Шаг 3: Объединить подсписок в outputp.

Повторите для оставшихся элементов в input и текущих элементов в output.

Сложность:
В лучшем: O(n)
В худшем: O(n^2)

Битоническая сортировка

Алгоритм сортировки, названный в честь понятия «битонической последовательности».

Для эффективной работы алгоритма длина списка должна быть степенью 2.

Шаг 1: Разделите список на две равные половины. Отсортируйте каждую половину таким образом, чтобы она стала битонической последовательностью.
Шаг 2: Битоническое слияние. Слияние предполагает сравнение элементов из обеих последовательностей и их перестановку для сохранения битонического свойства.
Шаг 3: Продолжайте делить последовательности на половины и объединять их, пока не получите одну полную отсортированную битоническую последовательность.
Шаг 4: После получения отсортированной битонической последовательности переверните ее, чтобы отсортировать в желаемом порядке (по возрастанию или по убыванию).

Сложность: O(log^2n)

Stooge Sort

Простой алгоритм сортировки, который использует рекурсию для упорядочивания элементов в массиве. Он был разработан в 1970 году языком программирования Чарльзом Хоаром, но получил свое название благодаря трём бестолковым импровизаторам (stooges) в комедийном эпизоде.

Алгоритм:
Берём отрезок массива (вначале это весь массив) и сравниваем элементы на концах отрезка. Если слева больше чем справа, то, естественно, меняем местами.
Затем, если в отрезке не менее трёх элементов, то тогда:
1) вызываем Stooge sort для первых 2/3 отрезка;
2) вызываем Stooge sort для последних 2/3 отрезка;
3) снова вызываем Stooge sort для первых 2/3 отрезка.

Сложность: O(n^(log3/log1.5))