Сортировка подсчетом.

Данный метод сортировки относится к простейшим методам. Его нечасто встретишь на практике. Он заключается в подсчете количества элементов, которые идут до текущего элемента. Например, если элемент является десятым в массиве, то он больше, чем девять предшествующих ему элементов. Таким образом, мы проходим для каждого элемента по всему массиву и считаем, сколько элементов меньше его. Для подсчета используется дополнительный массив, который и будет затем содержать отсортированные элементы. Итак, если элемент больше, чем k предшествующих ему элементов, то он займет позицию k + 1. Вот и все. В нашем примере мы не учитываем дубликаты, поэтому в этом случае вам придется немного модифицировать алгоритм.

Реализация алгоритма на языке Java:

Реализация алгоритма на языке Си:

Временная сложность данного алгоритма оценивается как O(N^2).

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *