无序序列中O(n)时间复杂度寻找最小(最大)的K个数

一、快速排序，平均复杂度为n*logn

二、维护K个最小(最大)堆，平均复杂度为n*logK

三、类似快排的划分方法

寻找N个数中最大的K个数，本质上就是寻找最大的K个数中最小的那个，也就是第K大的数。

可以使用二分搜索的策略来寻找N个数中的第K大的数。对于一个给定的数p，可以在O（N）的时间复杂度内找出所有不小于p的数。

寻找第k大的元素：

#include <iostream>
using namespace std;

//快速排序的划分函数
int partition(int a[],int l,int r)
{
    int i,j,x,temp;
    i = l;
    j = r+1;
    x = a[l];
    //将>=x的元素换到左边区域
    //将<=x的元素换到右边区域
    while (1)
    {
        while(a[++i] > x);
        while(a[--j] < x);
        if(i >= j) break;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    a[l] = a[j];
    a[j] = x;
    return j;
}

//随机划分函数<span style="color:#ff0000;">（注：也可以使用无分化中项的中项方法，或者中位数的中位数方法来划分，不然无法达到O(n)的复杂度）
</span>int random_partition(int a[],int l,int r)
{
    int i = l+rand()%(r-l+1);//生产随机数
    int temp = a[i];
    a[i] = a[l];
    a[l] = temp;
    return partition(a,l,r);//调用划分函数
}

//线性寻找第k大的数
int random_select(int a[],int l,int r,int k)
{
    int i,j;
    if (l == r) //递归结束
    {
        return a[l];
    }
    i = random_partition(a,l,r);//划分
    j = i-l+1;
    if(k == j) //递归结束，找到第K大的数
        return a[i];
    if(k < j)
    {
        return random_select(a,l,i-1,k);//递归调用，在前面部分查找第K大的数
    }
    else
        return random_select(a,i+1,r,k-j);//递归调用，在后面部分查找第K大的数
}

int main()
{
    int a[]={1,2,3,4,6,6,7,8,10,10};

    cout<<random_select(a,0,9,1)<<endl;
    cout<<random_select(a,0,9,5)<<endl;
    return 0;
}