Who’s in the middle

快速排序

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 10010;
int a[N];                                      //存数据
int quicksort(int left, int right, int k){
  int mid = a[left + (right - left) / 2];
  int i = left, j = right - 1;
  while(i <= j){
    while(a[i] < mid) ++i;                    //左边小于mid
    while(a[j] > mid) --j;                    //右边大于mid
    if(i <= j){                               //i大于j不处理
      swap(a[i], a[j]);                       //交换j和i
      ++i;--j;                                //逼近mid
    }
  }
  if(left <= j && k <= j) return quicksort(left, j + 1, k);    //j+1避免k值是最大的特例，陷入死循环
  if(i < right && k >= i) return quicksort(i, right, k);       //带有K值的排序
  return a[k];                                                 //返回第k大数
}
int main(){
  int n; scanf("%d", &n);
  for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    int k = n/2;
  printf("%d\n", quicksort(0, n, k));
  return 0;
}

笔记：这个快速排序是针对题意修改后的，每次递归的只有包含k元素，这样时间复杂度只能比全部的快速排列小，只要不是特例，时间肯定会快一些