Изменения
Нет описания правки
Пусть далее исходня последовательность из n структур хранится в массиве С, а отсортированная - в А, причем ее ключи принадлежат множеству 0..k.
Избавиться от этих недостатков можно следующим образом.
* Подсчитаем количество разных ключей в списке (пусть их будет k), а также количество ключей каждого вида. Пусть массив Р[i] содержит количество ключей, равных i. Очевидно, что это делается за О(n).
* Пусть для определенности P[1], P[2], ..., P[k] не равны нулю. Тогда разобьем Разобьем массив А на k блоков, длина каждого из которых равна соотв. P[1], P[2], ..., P[k], и поставим над первым элементом каждого блока по указателю point_i, который в дальнейшем будет указывать на первый свободный элемент в своем блоке i.
* Теперь массив Р нам больше не нужен. Тогда превратим его в массив, хранящий в Р[i] - сумму элементов от 0 до i - 1 старого массива Р. Это делается за один пробег по массиву.
* Теперь собственно сортировка. Как мы определим Для определения на очередном шаге по массиву С, куда вставить текущий элемент? Очень просто. Посмотрим посмотрим на поле key и запишем эту структурку в <tex>A[P[key] + point_{key}]</tex>. Затем увеличим соотв. значение указателя на 1. Таким образом, после завершения алгоритма в А будет содержаться наша последовательность в отсортированном виде (так как блоки расположены по возрастанию соотв. ключей).
Стоит также отметить, что эта сортировка устойчивая, так как два элемента с одинаковыми ключами будут добавлены в том же порядке, в котором просматривались в изначальном массиве.
