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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 public static void countSort(List<Integer> 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 содержит отрицательные числа, приведенный ниже код позволяет решить эту проблему.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 public static void countSort(List<Integer> 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++