寻找最小的k个数（四种方法）-白红宇

1 使用从大到小的优先队列保存最小的K个数，每次取出K个数之后的其余数和堆顶元素比较，如果比堆顶元素小，则将堆顶元素删除，将该元素插入

void topK(int arr[],int n,int k){    if(k>n)        return;    priority_queue
     
       q;    for(int i=0;i

2 使用set的排序功能，以从大到小的顺序排序所有前K个元素，取出其余的元素与第一个元素比较，如果小于第一个元素，则将第一个元素删除，将当前元素插入。

void topK1(int arr[],int n,int k){    set
     
      
        > st;    if(k>n)        return;    for(int i=0;i
       
        arr[i])            {                st.erase(iter);                st.insert(arr[i]);            }        }    }    auto iter=st.begin();    while(iter!=st.end())    {        cout<<*iter++<<' ';    }    cout<

3 使用partition的方法，每次找出一个数的固定位置index，其中左边的元素都比该元素小，右边的元素都比该元素大。如果index==k-1，则结束循环，找出的index及之前的元素就是k个最小的元素，否则如果index

大于k-1，则需要找的元素在index的左边，否则需要找的元素在index的右边。循环查找直到index==k-1。

int partition(int arr[],int s,int e){    int priov=arr[e];    int i=s-1;    int j=s;    for(;j

4 利用选择排序的功能，n个元素中找出最小值与第一个元素交换，从n-1个元素中找出次小值与第二个元素交换，直到找到k个元素位置。

void topK3(int arr[],int n,int k){    for(int i=0;i