求一个数组中第k大的数方法

求一个数组中第k大的数，

我第一印象是冒泡，因为只要冒泡k趟即可，第一趟冒泡第一大，第二次冒泡第二大，第k次冒泡第k大，时间复杂度为O(kn), n为数组长度。

但是我们都知道快速排序是对冒泡的改进，降低冒泡的递归深度，使时间复杂度降低到O(nlgn)，为什么不用快排呢？那么快排的时间复杂度又是多少呢？

因为快排每次将数组划分为两组加一个枢纽元素，每一趟划分你只需要将k与枢纽元素的下标进行比较，

如果比枢纽元素下标大就从右边的子数组中找，如果比枢纽元素下标小从左边的子数组中找，如果一样则就是枢纽元素，找到，如果需要从左边或者右边的子数组中再查找的话，只需要递归一边查找即可，无需像快排一样两边都需要递归，所以复杂度必然降低。

最差情况如下：假设快排每次都平均划分，但是都不在枢纽元素上找到第k大

第一趟快排没找到，时间复杂度为O(n)，第二趟也没找到，时间复杂度为O(n/2)，。。。。。，第k趟找到，时间复杂度为O(n/2k)，所以总的时间复杂度为

O(n(1+1/2+....+1/2k))=O(n)，明显比冒泡快，虽然递归深度是一样的，但是每一趟时间复杂度降低。

一。快排。借用了快排的partition思想，其实是一种分治的方法。对于一个partition，他左边的数小于他，右边的数全大于他

那么：

　　1.如果他本身就是第K个数，直接返回。

　　2.如果他的下标是比K大的某个数，那么第K小数肯定出现在他左边。那么到partition的左边递归地求解

　　3.如果他的下标是比K小的某个数，那么第K小数肯定出现在他右边。那么到partition的右边递归地求解

唯一需要注意的地方是，要注意在递归的过程中,第K小数是一个相对值，即相对于区间[l，r]的左边界l；

快排求第k大数代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000;
int a[maxn];
int n = 10,k = 6;

int part(int low, int high)
{
    int pivot = a[low];
    while(low < high){
        while(low < high&&a[high] >= pivot) high--;
        a[low] = a[high];
        while(low < high&&a[low] <= pivot) low++;
        a[high] = a[low];
    }
    a[low]=pivot;
    return low;
};

int quicksort(int l, int r, int k){
    int pos = part(l,r);
    if(pos - l + 1 == k) return a[pos];
    else if(pos - l + 1> k) return quicksort(l,pos-1,k);
    else return quicksort(pos+1,r,k-(pos-l+1));
}

int main()
{
    srand((unsigned)time(NULL));
    for(int i = 0; i < n; ++i){
        a[i] = rand()%(n<<1);
    }
    for(int i = 0; i < n; ++i)
        printf("%d ",a[i]);
    printf("\n");
    int x = quicksort(0,n-1,k);
    printf("%d\n", x);
}

二、小顶堆

使用堆可以求出最小的元素，通过不断地弹出元素，就可以找到第K大的元素

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000;
int a[maxn];
int n,k;

void adjust_heap(int rt,int n)
{
    int x=a[rt],pos = rt;
    while(rt <= n){
        int lc = rt << 1,rc = lc|1;
        if(lc <= n&&a[lc] < x) pos = lc;
        if(rc <= n&&a[rc] < a[pos]) pos = rc;
        if(pos == rt) break;
        a[rt] = a[pos];
        rt = pos;
    }
    a[pos] = x;
}

int search_k()
{
    for(int i = n/2;i >= 1; --i){//建堆的复杂度是O（n）的
        adjust_heap(i,n);
    }
    int sz = n;
    for(int i = 1; i < k; ++i){//每次弹出要向下调整，调整K次，复杂度为O（Klogn）
        a[1] = a[sz--];
        adjust_heap(1,sz);
    }
    return a[1];
}
int main()
{
    srand((unsigned)time(NULL));
    scanf("%d%d",&n,&k);
    for(int i = 1; i <= n; ++i){
        a[i] = rand()%(n<<1);
    }
    for(int i = 1; i <= n; ++i)
        printf("%d ",a[i]);
    printf("\n");
    int x = search_k();
    printf("%d\n", x);
}