Есть такой алгоритм. Называется
quickSelect. Фактически, это обрезанный quickSort, где после выбора ведущего элемента и разбивки массива работа продолжается только в той половине, где находится раздел между первыми K элементами и остальными N-K.
Пусть у вас N элементов в массиве и надо вернуть K минимальных. Тогда сортировка будет работать за O(N log N), а quickselect за O(N) в среднем*. В худшем случае может быть и квадратичное время работы, но этот случай практически невозможен, если реализация испольует случайные числа для выбора ведущего элемента.
Если же вы боитесь этого худшего случая, или считаете себя самим невезучим человеком за всю историю человечества (или боитесь, что злой хакер взломает генератор случайных чисел и передаст вашей программе специально составленный массив, чтобы ее подвесить), то есть другой алгоритм, всегда работающий за O(n log k). При маленьких k - может быть даже быстрее первого алгоритма.
Суть его в том, чтобы в куче (heap aka priority queue) поддерживать пока найденные K минимальных элементов. При этом куча будет на максимум. Сначала туда кладутся первые k элементов массива, а потом каждый следующий вытесняет максимальный элемент в куче, если он его меньше.
* Вообще говоря, можно заставить quickselect и quicksort работать идеально всегда, если использовать алгоритм
Блюма-Флойда-Пратта-Ривеста-Тарьяна, который ищет медиану за O(n). Но на практике этот алгоритм не применятеся, потому что у него такая константа, что там на логарифм хватит и еще на квадрат останется.
