Изменения

Перейти к: навигация, поиск

Поиск k-ой порядковой статистики

66 байт добавлено, 20:48, 14 мая 2011
Код алгоритма
Ниже представлен код представленного алгоритма. При реализации, однако, вместо рекурсивных вызовов изменяются границы поиска статистики во внешнем цикле. В коде счититаем, что процедура '''partition''' принимает массив и границы отрезка, который будет рассечён (причём правая граница отрезка не включается) и возвращает индекс опорного элемента. Также, считается, что массив индексируется с нуля.
'''int ''' findOrderStatistic('''int[] ''' array, '''int ''' k) { '''int ''' left = 0, right = array.length; '''while ''' ('''true''') { '''int ''' mid = partition(array, left, right);
'''if ''' (mid == k) { '''return ''' array[mid];
}
'''else if ''' (k < mid) {
right = mid;
}
'''else ''' {
k -= mid + 1;
left = mid + 1;
Анонимный участник

Навигация