利用快速排序的思想：

数组长度为n
寻找一个数k, 最简单的方式是取第一个数
比k小的都在其左边，比k大的都在右边
如果k所在数组的位置求区间第K大 - 图1 恰好为n-k，即为第k大
如果求区间第K大 - 图2 则在右边寻找
否则在左边寻找
查找时间复杂度为 求区间第K大 - 图3

void Find(int l, int r) {
    int pos = partition(l, r);
    if (pos == n - k) cout << a[pos] << endl;
    else if (pos < n - k) Find(pos + 1, r);
    else Find(l, pos - 1);
}

利用partition 函数记录位置, 复杂度求区间第K大 - 图4

int partition(int left, int right) {
    int tmp = a[left];  // 存储标记位置的值
    while (left < right) {
        while (a[right]>tmp&&right)right--;
        swap(a[right], a[left]);
        while (a[left]< tmp&&left<n)left++;
        swap(a[left], a[right]);
    }
    a[left] = tmp; 
    return left;     
}

输入数据，调用

#include<iostream>
#include<algorithm>
using namespace std;
#define _for(i,a,b) for(int i=(a);i<b;i++)
const int N = 1e6;
int a[N];
int n;
int k;
int main() {
    cin >> n>>k;
    _for(i, 0, n) cin >> a[i];
    Find(0, n-1);
    return 0;
}

优化：改进K的选取

传入参数为vector v,k : vector 表示要进行查找的数据容器
创建一个二维容器v2，表示分组表
为每一组创建一个容器，存入5个数据

n = v.size(),共有n//5个分组

void Select(vector<int> v, int k)
vector<vector<int>> v2;
  int n = v.size();
  _for(j, 0, n / 5) {
    vector<int>v1;
    _for(i, j*5, (j+1) * 5) {
      v1.push_back(v[i]);
    }
    sort(v1.begin(), v1.end(),greater<int>());
    v2.push_back(v1);
  }

对每一组按照组内的中位数的大小作为key，进行排序

bool cmp(vector<int>v1, vector<int>v2) {
  return v1[v1.size() / 2] < v2[v2.size()/2];
}

if (v2.size()) 
      sort(v2.begin(), v2.end(), cmp); 
// 如果把最后数量不足5的一组在排序之前放进v2，对每组排序过后出现一个问题，有可能出现第一个组不足5个而第二个组为5个

把每一组的中位数放进集合M,选取M的中位数为k ，相当于归约子问题求区间第K大 - 图6

也可以直接取到中间列对应的中位数

if (v2.size()) 
vector<int>m = v2[v2.size() / 2];// 中间列
k_hat= m[m.size() / 2];//中位数
k_hat_flag = 0;// 中位数已用的标记：在5分组中已用，当不能进行5分组时，标记为1，表示中位数在5分组余下的数中取

再对左上角，右下角与k进行比较，再分进S1，S2集合中，
再把左下角的数和右上角的数分别放入S1和S2中

if (v2.size()) {// 如果能够进行5分组
_for(col, 0, 2) {
      _for(row, 0, v2.size() / 2) {//左上角比较
        if (v2[row][col] < k) left.push_back(v2[row][col]);
        else right.push_back(v2[row][col]);
      }
      _for(row, v2.size() / 2 + 1, v2.size()) //右上角加入到right容器
        right.push_back(v2[row][col]);
    }
 _for(col, 3, 5) {
      _for(row, v2.size() / 2 + 1, v2.size()) {//右下角比较
        if (v2[row][col] < k) left.push_back(v2[row][col]);
        else right.push_back(v2[row][col]);
      }
      _for(row, 0, v2.size() / 2)//左下角加入到left容器
        left.push_back(v2[row][col]);
    }
}

把中位数所在的行与列的数对应放到S1与S2集合，就是left和right容器

_for(i, 0, m.size() / 2)right.push_back(m[i]); //中间列的上方加入
_for(i, m.size() / 2 + 1, m.size())left.push_back(m[i]);//中间列的下方加入
_for(col, 0, v2.size() / 2)left.push_back(v2[col][2]);// 对中间一行前面进行遍历
_for(col, v2.size() / 2 + 1, v2.size())right.push_back(v2[col][2]);// 对中间一行后面进行遍历

把中位数与五分组后剩下的数进行比较，加入到对应的集合，
如果上面没有取得中位数，则在剩下的数中取中位数：排序取中位数的下界

if (n % 5) { // 所以最后再来比较不足5的一组
      if (k_hat_flag) { sort(v.begin(), v.end());k_hat = v[(v.size()-1) / 2]; }
      _for(i, 0, n % 5) {
          if (v[n - i - 1] > k_hat) right.push_back(v[n - i - 1]);
          else  left.push_back(v[n - i - 1]);
      }
  }

对这两个集合进行子问题归约

if (k == right.size() + 1) {
      cout << k_hat << endl;return;
  }
  else if (k <= right.size())Select(right, k);
  else Select(left, k);

输入数据调用查找第K大函数

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define _for(i,a,b) for(int i=(a);i<(b);i++)
int n;
int k;
int main() {
  cin >> n>> k;
  vector <int> v;
  int x;
  _for(i, 0, n) {
      cin >> x;
      v.push_back(x);
  }
  Select(v, k);
  return 0;
}

讨论：

如果要查找第k小，只需把递归调用部分的right.size()改为left.size()

调用API

```c

include

using namespace std; int main() { std::vector v; int x, n, k; cin >> n >> k; for (int i = 0;i < n;i++) {

  cin >> x;
  v.push_back(x);

} nth_element(v.begin(), v.begin() + k, v.end(), std::greater()); cout << v[k-1] << endl; }

```

求第二大
如果只有2个数：
比较一次
如果有3个数：2 5 6
分成两组：2 5：5晋级
5 6 6晋级：
取第二大 5

如果有4个数：
2 5 6 9
2，5：5晋级
6，9：9晋级