101
правка
Изменения
м
Пояснения
== Использование списков ==
Сначала расскажем как делать <b>не нужно</b>. <br>
Пусть далее исходная последовательность из <tex>n</tex> структур хранится в массиве <tex>A</tex>, а отсортированная {{---}} в массиве <tex>P</tex> с индексами от <tex>0</tex> до <tex>k-1</tex>.
Исходная последовательность из <tex>n</tex> структур хранится в массиве <tex>A</tex>, а отсортированная {{---}} в массиве <tex>B</tex> того же размера. Кроме того, используется вспомогательный массив <tex>P</tex> с индексами от <tex>0</tex> до <tex>k-1</tex>.
Идея алгоритма состоит в предварительном подсчете количества элементов с различными ключами в исходном массиве и разделении результирующего массива на части соответствующей длины(будем называть их блоками). Затем при повторном проходе исходного массива каждый его элемент копируется в специально отведенный его ключу блок, в первую свободную ячейку. Это осуществляется с помощью массива индексов <tex>P</tex>, в котором хранятся индексы начала блоков для различных ключей. <tex>P[key]</tex> {{---}} индекс в результирующем массиве, соответствующий первому элементу блока для ключа <tex>key</tex>.
* Пройдем по исходному массиву <tex>A</tex> и запишем в <tex>P[i]</tex> количество структур, ключ которых равен <tex>i</tex>.
