Quick Select

Код алгоритма:

  public static int quickselect(int[] array, int k) {
    int start = 0;
    int end = array.length - 1;
    while (true) {
      if (start < end) {
          swap(array, start, ThreadLocalRandom.current().nextInt(start, end));
      }
      int pivot = array[start];
      int left = start + 1;
      int right = end;
      while (left <= right) {
        if (array[left] > pivot && array[right] < pivot) {
          swap(array, left, right);
          left++;
          right--;
        }
        if (array[left] <= pivot) {
          left++;
        }
        if (array[right] >= pivot) {
          right--;
        }
      }
      swap(array, start, right);
      if (right == k - 1) {
        return array[right];
      }
      if (right > k - 1) {
        end = right - 1;
      } else {
        start = right + 1;
      }
    }
  }

  private static void swap(int[] array, int i, int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
  }