分治专题 输出前k大的数

给定一个数组，统计前k大的数并且把这k个数从大到小输出。

分治：把一个问题分解成形式和原任务相同，但规模更小的几个部分任务（通常是两个部分），分别完成，或只需要选一部分完成。然后再处理完成后的这一个或几个部分的结果，实现整个任务的完成。

把前m大的都弄到数组的右边，然后对最右边的m个元素排序再输出。
O（n）时间内实现把前m大的都弄到数组最右边。

arrangeRinght(int l, int r, int k):把数组[l, r]前k大的都弄到最右边。（类似快排）

#include<bits/stdc++.h>
using namespace std;

int a[100005], n;

void arrangeRinght(int l, int r, int k)
{
    int i=l, j=r;
    while(i<j)
    {
        while(i<j&&a[j]>=a[i])
            j--;
        swap(a[i], a[j]);
        while(i<j&&a[j]>=a[i])
            i++;
        swap(a[i], a[j]);
    }
    
    //分治
    if(r-i+1==k)
        return;
    if(r-i+1>k)
        arrangeRinght(i+1, r, k);//后半部分
    if(r-i+1<k)
        arrangeRinght(l, i-1, k-(r-i+1));//前半部分

}

int main()
{
    int k;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&k);
    arrangeRinght(1, n, k);
    sort(a+n-k, a+n+1);
    for(int i=n;i>=n-k+1;i--)
    {
        cout<<a[i]<<endl;
    }

    return 0;
}