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

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

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

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++