355
правок
Изменения
→Решение
== Решение ==
Пусть далее исходня последовательность из n структур хранится в массиве С, а отсортированная - в А, причем ее ключи принапринадлежат множеству 0..k.
Как можно модифицировать алгоритм? Например, сделать изкаждой ячейки массива А список, в который будем добавлять структуры с одинаковыми ключами. Однако, этот вариант плох тем, что надо поддерживать сам список, что не является самым простым решением. К тому же нам надо будет хранить дополнительную информацию в виде ссылок на следующий элемент в списке.
Стоит также отметить, что эта сортировка устойчивая, так как два элемента с одинаковыми ключами будут добавлены в том же порядке, в котором просматривались в изначальном массиве.
==Источники==
* [http://en.wikipedia.org/wiki/Counting_sort Wikipedia | Count_sort]
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 224-226.
