K-я порядковая статистика
Пусть дан массив $A$ длиной $N$ и пусть дано число $K$. Задача заключается в том, чтобы найти в этом массиве $K$-ое по величине число, т.е. $K$-ую порядковую статистику.
Давайте поймем, что в быстрой сортировке мы можем узнать, сколько элементов меньше данного, тогда рассмотрим три случая
1) количество чисел, меньше данного = $k - 1$, тогда наше число - ответ.
2) количество чисел, меньше данного >= $k$, тогда спускаемся рекурсивно в левую часть и ищем там ответ.
3) количество чисел, меньше данного < $k$, спускаемся в правую ищем ($k$ - левая - 1) - ое число.
За сколько же это работает, из быстрой сортировки мы имеем, что размер убывает приблизительно в 2 раза, тогда если мы просуммируем размеры массивов на каждом этапе, мы получим $\sum_{k=1}^n \frac{n}{2 ^ k} = O(n)$.
Также в с++ эта функция уже реализована :
1 nth_element(указатель на начало, указатель на нужный элемент, указатель на конец);