main函数

#include <iostream>
#include <vector>
using namespace std;

int main(void) {
  int n, k;
  scanf("%d%d", &n, &k);
  if (n <= 0 || k <= 0 || k > n) {
    puts("");
    return 0;
  }
  vector<int> vec(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &vec[i]);
  }
  quickSelect(&vec[0], 0, n - 1, k);
  printf("%d\n", vec[k - 1]);
  return 0;
}

左右指针不取右，j和j+1

void quickSelect(int* arr, int left, int right, int k) {
  if (left >= right) {
    return;
  }
  int pivot = arr[left + ((right - left) >> 1)];
  int i = left - 1;
  int j = right + 1;
  while (i < j) {
    while (arr[++i] < pivot) {
    }
    while (arr[--j] > pivot) {
    }
    if (i < j) {
      swap(arr[i], arr[j]);
    }
  }
  int leftSize = j - left + 1;
  if (k <= leftSize) {
    quickSelect(arr, left, j, k);
    return;
  }
  quickSelect(arr, j + 1, right, k - leftSize);
}

左右指针不取左，i-1和i

void quickSelect(int* arr, int left, int right, int k) {
  if (left >= right) {
    return;
  }
  int pivot = arr[(static_cast<int64_t>(left) + right + 1) >> 1];
  int i = left - 1;
  int j = right + 1;
  while (i < j) {
    while (arr[++i] < pivot) {
    }
    while (arr[--j] > pivot) {
    }
    if (i < j) {
      swap(arr[i], arr[j]);
    }
  }
  int leftSize = i - left;
  if (k <= leftSize) {
    quickSelect(arr, left, i - 1, k);
    return;
  }
  quickSelect(arr, i, right, k - leftSize);
}

快慢指针取左

void quickSelect(int* arr, int left, int right, int k) {
  if (left >= right) {
    return;
  }
  int pivot = arr[left];
  int i = left;
  int j = left + 1;
  while (j <= right) {
    if (arr[j] < pivot) {
      ++i;
      swap(arr[i], arr[j]);
    }
    ++j;
  }
  swap(arr[i], arr[left]);
  int leftSize = i - left + 1;
  if (k == leftSize) {
    return;
  }
  if (k < leftSize) {
    quickSelect(arr, left, i - 1, k);
    return;
  }
  quickSelect(arr, i + 1, right, k - leftSize);
}

快慢指针取右

void quickSelect(int* arr, int left, int right, int k) {
  if (left >= right) {
    return;
  }
  int pivot = arr[right];
  int i = left - 1;
  int j = left;
  while (j < right) {
    if (arr[j] < pivot) {
      ++i;
      swap(arr[i], arr[j]);
    }
    ++j;
  }
  ++i;
  swap(arr[i], arr[right]);
  int leftSize = i - left + 1;
  if (k == leftSize) {
    return;
  }
  if (k < leftSize) {
    quickSelect(arr, left, i - 1, k);
    return;
  }
  quickSelect(arr, i + 1, right, k - leftSize);
}