Сортировка подсчетом (Count Sort)(реализация на языке Java)

Java   24 марта 2012  Автор статьи:  

Ниже представлена функция которая производит числовую сортировку структуры типа List, содержащей целочисленные элементы.

public static void countSort(List array) {
int[] c = new int[Collections.max(array) + 1];
//создаем массив с, содержащий количество вхождений в array
//элемента х
for (int x : array) {
c[x]++;
}
int n = 0;
//вставляем элементы в массив array в порядке возрастания
for (int i = 0; i < c.length; i++) { for (int j = 0; j < c[i]; j++) { array.set(n++, i); } } }

Заметим, что при большом разбросе значений в массиве array, массив с приобретает слишком большие размеры, из-за чего сортировка будет значительно терять в своей скорости.

Приведенный выше код не работает в том случае, если массив array содержит отрицательные числа, приведенный ниже код позволяет решить эту проблему.

public static void countSort(List array) {
int l = Collections.min(array);
int r = Collections.max(array);
int[] c = new int[r-l+1];
//создаем массив с, содержащий количество вхождений в array
//элемента х
for (int x : array) {
c[x-l]++;
}
int n = 0;
//вставляем элементы в массив array в порядке возрастания
for (int i = 0; i < c.length; i++) { for (int j = 0; j < c[i]; j++) { array.set(n++, i+l); } } }

Этот код будет сортировать листы с отрицательным элементами. Заметим, что и в этом случае для корректной и быстрой работы алгоритма расстояние между array.min и array.max должно быть небольшим(не более 100).
Вместо стандартных массивов мы могли бы использовать Map, однако для правильной работы ключи в map должны быть отсортированы, а стандартно они сортируются за O(nlogn), что делает использование countsort нецелесообразным.

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

  • на Delphi

  • на Java

  • на C++