Вот несколько распространенных алгоритмов сортировки, реализованных в C++:

1. Пузырьковая сортировка:

   • Пузырьковая сортировка – это простой алгоритм сортировки на основе сравнения. Он неоднократно проходит по списку, сравнивает соседние элементы и меняет их местами, если они расположены в неправильном порядке.

2. Сортировка выбором:

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

3. Сортировка вставками:

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

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

   • Сортировка слиянием – это алгоритм «разделяй и властвуй», который делит входной массив на две половины, рекурсивно сортирует каждую половину, а затем объединяет отсортированные половины для получения отсортированного вывода.

5. Быстрая сортировка:

   • Быстрая сортировка — это алгоритм «разделяй и властвуй», который работает путем выбора опорного элемента и разделения остальных элементов на два подмассива в зависимости от того, меньше они или больше опорного элемента. Затем он рекурсивно сортирует подмассивы.

6. Кучная сортировка:

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

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

   • Поразрядная сортировка – это алгоритм несравнительной сортировки, который сортирует данные с помощью целочисленных ключей путем группировки ключей по отдельным цифрам, имеющим одинаковую значащую позицию и значение.

8. Сортировка по подсчету:

   • Сортировка по подсчету – это алгоритм сортировки целых чисел, который подсчитывает количество вхождений каждого уникального элемента во входном массиве и использует арифметические действия для вычисления положения каждого элемента в выходном массиве.

   • Сортировка сегментов:

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

   • Сортировка оболочки:

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

   • Сортировка коктейлей:

     • Коктейльная сортировка – это разновидность пузырьковой сортировки, при которой список сортируется в обоих направлениях: по возрастанию или по убыванию. Он неоднократно проходит по списку, сравнивая соседние элементы и меняя их местами при необходимости.

   • Комбинированная сортировка:

     • Гребенчатая сортировка – это разновидность пузырьковой сортировки, которая работает путем сравнения и замены элементов с большим зазором, который уменьшается с каждой итерацией. Это похоже на пузырьковую сортировку, но более эффективно.