277
правок
Изменения
Нет описания правки
== Основная идея ==
== Простой алгоритм ==
== Устойчивый алгоритм ==
==== Идея ====
Основная идея состоит в том, чтобы для каждого элемента входного массива подсчитать количество элементов, меньших данного. Эта информация будет указывать на позиции элементов в отсортированном массиве. Например, если для элемента <tex>x</tex> количество таких элементов будет <tex>42</tex>, то <tex>x</tex> будет занимать <tex>43</tex>-ю позицию в отсортированном массиве. Если элементы могут иметь одинаковые значения, то необходимо модифицировать алгоритм, так как нельзя разместить все такие элементы в одну позицию.
==== Реализация ====
В этом варианте помимо входного массива <tex>A</tex> потребуется два вспомогательных массива — <tex>C[0..k - 1]</tex> для счётчика и <tex>B[0..n - 1]</tex> для отсортированного массива. Сначала следует заполнить массив <tex>C</tex> нулями, и для каждого <tex>A[i]</tex> увеличить <tex>C[A[i]]</tex> на 1. Далее подсчитывается число элементов меньше или равных текущему. Для этого каждый <tex>C[number]</tex>, начиная с <tex>C[1]</tex>, увеличивают на <tex>C[number - 1]</tex>. На последнем шаге алгоритма читается входной массив с конца и в каждый <tex>B[C[A[i]]]</tex> записывается <tex>A[i]</tex>, а значение <tex>C[A[i]]</tex> уменьшается на 1. Алгоритм устойчив. Устойчивость может потребоваться при [[Сортировка_подсчетом_сложных_объектов|сортировке сложных структур данных]].
<code>
