@$$RaMpAgE

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

0

@PointsEqual

сравнение из википедии:

Сортировка выбором (Selection sort) — Сложность алгоритма: O(n2);
Сортировка Шелла (Shell sort) — Сложность алгоритма: O(n log2 n);
Сортировка расчёской (Comb sort) — Сложность алгоритма: O(n log n)
Пирамидальная сортировка (Сортировка кучи, Heapsort) — Сложность алгоритма: O(n log n); п
Плавная сортировка (Smoothsort) — Сложность алгоритма: O(n log n)
Быстрая сортировка (Quicksort) — Сложность алгоритма: O(n log n) — среднее время, O(n2) — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
Introsort — Сложность алгоритма: O(n log n), сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает log(n).
Patience sorting — Сложность алгоритма: O(n log n + k) — наихудший случай, требует дополнительно O(n + k) памяти, также находит самую длинную увеличивающуюся подпоследовательность
Stooge sort — рекурсивный алгоритм сортировки с временной сложностью .
Поразрядная сортировка — Сложность алгоритма: O(n·k); требуется O(k) дополнительной памяти.

3

@MILAN

Алгоритмы сортировок

1

@fasked

$$RaMpAgE, разные сортировки оптимальны для разных наборов данных. Есть очень красивый ресурс, который показывает процесс сортировки крайних случаев, все анимированно и очень красиво.

7

UnderFelixAbove

Знать все сортировки может быть ни к чему. Важно понимать, что сортировки отличаются алгоритмической сложностью и их можно разбить на три класса в зависимости от уровня сложности (O(N*N), O(N*log(N)) и O(N)). Для каждого класса можно выбрать по две-три и досканально их изучить.
Среди квадратичных сортировок можно выделить:
1. Вставками
2. Выбором
Неплохой визуализатор можно поглядеть здесь: ссылка. Сортировку пузырьком не буду приводить в этом списке. Та же сортировка выбором пишется не дольше и для понимания не чуть не сложнее, не говоря уже о том, что работает она в два раза быстрее.

Среди "быстрых" можно посмотреть:
3. Быстрая. (Пожалуй самая популярная)
4. Слиянием. (Не сложная, но требующая дополнительную память + имеет рекурсивную реализацию)
5*. Пирамидальная. (Требует знания и понимания структуры данных КУЧА)

Визуализаторы можно найти здесь: ссылка

Линейные сортировки:
6. Подсчетом
7. Поразрядная.
Но здесь тоже нужно понимать, когда следует их применять. Можно почитать Кнута, если будет тяжеловато, есть много источников в сети.

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

Для углубленного изучения можно рассмотреть Плавную сортировку. Она редко встречается. Но мне показалась довольно интересной с точки зрения реализации и понимания.
Описание Плавной сортировки с картинками можно посмотреть здесь