Классификация алгоритмов сортировки

Д.Кнут выделяет пять классов сортировок:

1. Класс обменных сортировок: элементы обмениваются местами, если он не упорядочены

2. Класс выбора - из неупордяченной последовательности тем или иным образом выбирается элемент, и помещается (просто добавляется в выходные последовательность, которая становится упорядоченной)

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

4. Класс сортировки подсчетом - основан на том, что свое окончательное место упорядоченной последовательности с номером j элемент занимает в том и только том случае, если в этой последовательности оказалось ровно j-1 элемент, меньшей (сортировка по возрастанию), или по больших элемент, то есть для упорядочивания, а точнее нахождения места в упорядоченной последовательности для элемента достаточно подсчитать количество меньших ключей.

5. Класс сортировок слиянием, основан на объединении двух или более упорядоченных последовательностей, из которых без возвратов можно получить новую упорядоченную последовательность, включающую элементы объединение. применяется во внешней сортировке.

1 - пузырек, алгоритм Хоару (quicksort)

2 - простой выбор (min/max), пирамидальная сортировка

3 - простая вставка, алгоритм Шелла, бинарная

4 - сравнение и подсчет, распределяющий обмена (часть карманной сортировки)

5 - слияние: естественное двухпутевое слияние, фиксированное двухпутевое слияние