Сортировка подсчетом (Сount Sort)

Сортировки   13 марта 2012  Автор статьи:  

Сортировка подсчетом является линейной сортировкой(время работы — O(n)), она неприменима для сортировки в общем случае, так как основана не на сравнениях. Эта сортировка используется для массивов с ключами особого вида(чаще всего это целые числа в небольшом диапазоне значений).

Пусть массив a содержит целые числа, принимающие значения в интервале [0..k-1], а с — массив целочисленный массив длины k, содержащий 0. Тогда алгоритм сортировки примет следующий вид:

  1. Для каждого  x \in a увеличим значение с[i] на 1, т.е. массив с будет хранить число вхождений элемента х в массив а
  2. Возьмем n = 0
  3. Запускаем в цикле i=0 до k.
  4. Для каждого i присваиваем a[n] = i. Увеличиваем n на 1. Проделываем это ровно с[i]-1 раз

Алгоритм также применим для объектов, ключами к которым являются числа от 0 до k-1. Для этого массив с будет состоять из очередей. Вместо увеличения с[i] на единицу будем добавлять элемент в очередь с[i], вместо i a[n] будем присваивать элемент, вытащенный из очереди, и повторять операцию будем ровно столько раз, сколько элементов в очереди с[i]

Научиться программировать

  • на Delphi

  • на Java

  • на C++