K-ая порядковая статистика (реализация на языке Java)

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

Функция kth(long[] array, int l, int r, int k) находит k-ую порядковую статистику на отрезка [l;r] массива array.

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
public static long kth(long[] array, int l, int r, int k) {
        int i = l;
        int j = r;
        //выбор опорного элемента производится случайным образом
        long x = array[l + random.nextInt(r - l + 1)];
        //разделение массива на 3 части по опорному элементу х
        while (i <= j) {
            while (array[i] < x) {
                i++;
            }
            while (array[j] > x) {
                j--;
            }
            if (i <= j) {
                long temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i++;
                j--;
            }
        }
        //проверка, в каком из блоков находится k
        //1-ый блок
        if (l <= k && k <= j) {
            return kth(l, j, k);
        }
        //2-ой блок
        if (i <= k && k <= r) {
            return kth(i, r, k);
        }
        //если k во втором блоке, возвращаем непосредственно a[k]
        return array[k];
    }

Первый раз функция вызывается из main следующим образом: kth(array,0,array.length-1,k).

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

  • на Delphi

  • на Java

  • на C++