快速排序优化

单纯的快速排序的时间复杂度为nlogn，而优化后为n+klogk

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void qucikSort(vector<int>& a,int low,int high,int k)
{
    if(low>=high)
    {
        return;
    }
    int key=a[low];
    int i=low,j=high;
    while(i<j)
    {
        while(i<j&&a[j]>=key)j--;
        a[i]=a[j];
        while(i<j&&a[i]<=key)i++;
        a[j]=a[i];

    }
    a[i]=key;
    if((j-low+1)>k)//注意边界及判断条件+1
    {
       qucikSort(a,low,j,k); 
    }
    else if((j-low+1)<k)
    {
         qucikSort(a,j+1,high,k-(j-low+1));
    }
    else
         return;      

}
int main()
{
    int N,K;
    while(cin>>N>>K)
    {
        vector<int> arr(N,0);
        for(int i=0;i<N;i++)
        {
            cin>>arr[i];
        }
        qucikSort(arr,0,N-1,K);
        sort(arr.begin(),arr.begin()+K);
        for(int i=0;i<K-1;i++)
        {
            cout<<arr[i]<<" ";
        }
        cout<<arr[K-1]<<endl;
    }
    return 0;
}