分治法的应用----求一个序列中第K大或第K小的数

思想

借助快速排序的划分思想，如果是求第K小的数，则一次划分所得到的基准元素的位置pivot即为第pivot+1小的数（数组下标从0开始）。将其和K进行比较，如果等于K，则输出元素即可，否则如果小于K，则说明第K小的值在其右边，应往右子序列递归查找，如果大于K，则说明在其左边，应往左子序列递归。
如果要求第K大的数，则应从右往左数，定义pos=right-pivot+1,得到的为第pos大的数，然后将该值与K比较，若大于K，则往pivot右边子序列递归查找，否则往左边子序列递归查找。需要注意的是，在往左边递归时，寻找的应是第K-pos大的数。

#include<iostream>

using namespace std;
const int MAX = 10;//序列长度

int Partiton(int a[], int left, int right) {//快速排序的划分
    int temp = a[left];
    while (left < right) {
        while (left < right && a[right] >= temp) right--;
        a[left] = a[right];
        while (left < right && a[left] <= temp) left++;
        a[right] = a[left];
    }
    a[left] = temp;
    return left;
}
//求序列[left,right]中第K小的数
int RandSelect_Min(int a[], int left, int right, int K) {
    if (left < right) {
        int pivot = Partiton(a, left, right);
        if (pivot + 1 == K)//找到了第K小的数
            return a[pivot];
        else if (pivot + 1 < K)//往右递归
            RandSelect_Min(a, pivot + 1, right, K);
        else//往左递归
            RandSelect_Min(a, left, pivot - 1, K);
    } else if (left == right && K == left + 1) {//序列只有一个元素，且为a[k-1]
        return a[left];
    } else {
        return -99999;//K的值不合法
    }
}
//求序列[left,right]中第K大的数
int RandSelect_Max(int a[], int left, int right, int K) {
    if (left < right) {
        int pivot = Partiton(a, left, right);
        int pos = right - pivot + 1;//为从右往左数，第pos大的数
        if (pos == K)
            return a[pivot];
        else if (pos > K)//pos位于K的左边，往右递归
            RandSelect_Max(a, pivot + 1, right, K);
        else//pos位于K的右边，往左递归
            RandSelect_Max(a, left, pivot - 1, K - pos);//此时K应为K-pos
    } else if (left == right && K == MAX - left) {//序列只有一个元素，且刚好为第K大
        return a[left];
    } else {
        return -99999;
    }
}

int main() {
    int a[MAX] = {2, 5, 1, 7, 10, 6, 9, 4, 3, 8};
    for (int i = 1; i <= 10; ++i) {
        cout << "第" << i << "小的数为：" << RandSelect_Min(a, 0, 9, i) << endl;
    }
    for (int i = 1; i <= 10; ++i) {
        cout << "第" << i << "大的数为：" << RandSelect_Max(a, 0, 9, i) << endl;
    }
    return 0;
}

典型实例

https://blog.csdn.net/qq_43643944/article/details/116072737