Цифровая сортировка (Radix Sort)(реализация на Java)

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

В данной статье мы реализуем цифровую сортировку на Java. В среднем цифровая сортировка работает лучше чем быстрая сортировка. Конечно Radix Sort реализуют в разных вариантах, но в данном примере я покажу реализацию основанную на побайтовом делении числа. Если вы захотите изменить данный алгоритм на другой вид, то вам достаточно будет изменить функцию dig256, которая возвращает число равное следующему сортируемому разряду. Т.е для десятичной сортировки можно было реализовать функцию digit как (n/(10^p)%10). Теперь в зависимости от длин чисел вам нужно будет выбрать K и понятно тогда, что массив c[i] содержал бы 10 элементов.
Ниже представлен код функций цифровой сортировки(radixSort) и операции dig256.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public static void radixSort(List<Integer> array) {
        //максимальное число байтов в числе
        int k = Integer.SIZE / 8;
        //число элементов в массиве
        int n = array.size();
        //двигаемся по байтам в числах
        for (int i = 0; i < k; i++) {
            //создаем массив с заполненый нулями, который
            //будет содержать количество элементов
            //содрежащих i-ый байт в k-ой позиции
            int[] c = new int[256];
            //заполняем массив с как в сортировке подсчетом
            for (int j = 0; j < n; j++) {
                c[dig256(array.get(j), i)]++;
            }
            //модифицируем массив с
            for (int j = 1; j < 256; j++) {
                c[j] += c[j - 1];
            }
            //массив b будет представлять отсоритровонную до
            //k-ого байта копию массива array
            Integer[] b = new Integer[n];
            for (int j = n - 1; j >= 0; j--) {
                b[--c[dig256(array.get(j), i)]] = array.get(j);
            }
            //заменяем массив аrray на b
            array.clear();
            array.addAll(Arrays.asList(b));

        }


    }

    //эта функция возвращает p-ый байт числа n
    public static int dig256(int n, int p) {
        return (n >> (8 * p)) & 255;
    }

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

  • на Delphi

  • на Java

  • на C++