5. 在数组中找到第k大的元素

在数组中找到第k大的元素

参考

1. 先排序，再查找。
   最简单，但是最麻烦，如果不止一次的使用数组中的第k大元素，那么可以先排序，以备后面继续使用。
2. 冒泡和选择
   使用冒泡和选择算法，直到排好了第k大元素以后结束。
   冒泡：从后向前，对比。
3. 快速排序的思想
   快排中，选取一个分割元素，然后交换两边元素直到分割元素左边大于右边（或相反），那么此时，这个分割元素就已经排好序了，对比分割元素的下标，可以知道第k大元素在分割元素之前还是之后，然后有选择的去递归另一边就好。
4. 桶排序
   适用于元素离散度不大的数组。
5. 二叉堆
   先使用二叉堆建一个k个元素最大堆，当继续想堆中添加元素，如果大于堆顶元素，舍去。小于堆顶元素，那么替换堆顶元素，重新建堆，保持堆的元素为k个。
   遍历结束以后，堆顶元素就是第k大元素。
   适用于内存有限，不能一次性读入内存的数据。

#include <iostream>
#include <algorithm>
#include <vector>
#include <unistd.h>
using namespace std;

void print(vector<int> &source)
{
    cout<<endl;
    for(auto i:source)
    {
        cout<<i<<" ";
    }
    cout<<endl;
}

//先排序，后查找
int findk1(int k,vector<int> &source)
{
    if(k>source.size())
    {
        return INT32_MIN;
    }
    int index = k-1;
    
    sort(source.begin(),source.end());
    return source[index];
}


//冒泡和选择排序
int findk21(int k,vector<int> &source)
{
    if(k>source.size())
    {
        return INT32_MIN;
    }
    int index = k-1;
    for(size_t i=0;i<source.size();i++)
    {
        for(size_t j = source.size()-1;j>i;j--)
        {
            if(source[j]<source[j-1])
            {
                swap(source[j],source[j-1]);
            }
        }
        print(source);
        
        if(i == index)
        {
            return source[index];
        }

    }
}

int findk22(int k,vector<int> &source)
{
    if(k>source.size())
    {
        return INT32_MIN;
    }
    int minIndex;
    for(size_t i = 0; i<source.size();i++)
    {
        minIndex=i;
        size_t j = i;
        for(;j<source.size();j++)
        {
            if(source[minIndex]>source[j])
            {
                minIndex=j;
            }
            cout<<"now :"<<source[j]<<" "<<source[j-1]<<" minIndex: "<<minIndex<<endl;
            
        }
        swap(source[minIndex],source[i]);
        print(source);
        if((k-1) == i)
        {
            return source[k-1];
        }
    }
}




//快排思想实现

int quicksortPartition(int start,int end,vector<int> &source)
{
    int x = source[end];
    int i = start-1;
    for(int j=start;j<end;j++)
    {
        if(source[j]<x)
        {
            i++;
            swap(source[i],source[j]);
        }
    }
    i++;
    swap(source[i],source[end]);

    cout<<endl;
    for(auto i:source)
    {
        cout<<i<<" ";
    }
    cout<<endl;

    return i;
}

int quicksort(int start,int end,vector<int> &source ,int k)
{
    if(start >= end)
    {
        return -1;
    }
    int i=quicksortPartition(start,end,source);
    if(i>k && i-1 != start)
    {
        quicksort(start,i-1,source,k);
    }else if((i)<k && i+1 != end){
        quicksort(i+1,end,source,k);
    }else{
        return source[i];
    }

}



int findk3(int k,vector<int> &source)
{
    if(k>source.size())
    {
        return INT32_MIN;
    }
    return quicksort(0,source.size()-1,source,k);
}





//堆排序
void heapsort_max(vector<int> &source,int i,int len=0)
{
    int l=i*2;
    int r=i*2+1;
    int maxIndex=i;
    len=len==0?source.size():len;
    if(l<len && source[l]>source[i])
    {   
        maxIndex=l;
    }
    if(r<len && source[r]>source[maxIndex])
    {
        maxIndex=r;
    }
    // cout<<"cur: "<<i<<" max :"<<maxIndex<<" left: "<<source[2*i]<<" right: "<<source[2*i+1]<<endl;
    if(maxIndex != i)
    {
        swap(source[i],source[maxIndex]);
        heapsort_max(source,maxIndex,len);
    }
}

void heapsort_sort(vector<int> &source)
{
    for(int i = source.size()-1;i>1;i--)
    {
        swap(source[1],source[i]);
        heapsort_max(source,1,i);
    
    }
}
void heapsort_build(vector<int> &source)
{
    for(int i = source.size()/2 + 1; i>0 ;i--)
    {
        heapsort_max(source,i);
    }
}
// int heapsort(vector<int> &source)
// {
//     heapsort_build(source);
//     heapsort_sort(source);
// }
int findk5(int k,vector<int> &source)
{
    if(k>source.size())
    {
        return INT32_MIN;
    }
    
    vector<int> tmp;
    tmp.push_back(0);
    
    for(int i=1;i<=k;i++)
    {
        tmp.push_back(source[i-1]);
    }
    heapsort_build(tmp);    
    for(int i=k;i<source.size();i++)
    {
        if(source[i]<tmp[1])
        {
            tmp[1]=source[i];
            heapsort_build(tmp);
        }
    }
    return tmp[1];
}
int main()
{
    vector<int> a{1,2,3,4,5,6,8,9,10,7};
    print(a);
    int k;
    while(cin>>k)
    {
        cout<<findk1(k,a)<<endl;;
        // print(a);
        // cout<<findk22(k,a)<<endl;
    }
}