Классы	Алгоритмы
Exchanging – Обменом	Bubble, Quick
Insertion - Вставками	Insert, Shell
Merge – Слиянием	Merge
Selection – Выбором	Select, Heap
Non-comparision - Распределением	Bucket, Counting, Binary Tree, Distribution

 

 

Пояснения по области применения.

 

Bubble

Эффективен он лишь для небольших массивов.

 

Quick

Сильно деградирует по скорости (до Θ(n²)) при неудачных выборах опорных элементов, что может случиться при неудачных входных данных. Этого можно избежать, используя такие модификации алгоритма, как Introsort или вероятностно, выбирая опорный элемент случайно, а не фиксированным образом.

 

Insertion

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

 

Shell

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

 

Merge

Часто используется для сортировки линейного списка.

Находит применение при потоковом чтении элементов, однако уступает в скорости сортировке бинарным деревом.

 

Selection

Малоэффективен для больших массивов. Оптимальная скорость достигается при количестве элементов меньшем 20.

 

Heap

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

 

Binary Tree

Данная сортировка является оптимальной при получении данных путём непосредственного чтения с потока (например, с файла, сокета или консоли).

 

Sorting Networks

Математическая модель, использующая параллельные компараторы. Найдены и доказаны эффективные алгоритмы для n<=8.

 

Bucket

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

 

Counting

Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000.