Variant quick platoon: find the largest number of top k

seek n The largest of the number K Number , Generally, you can think of selective sorting or heap sorting , Here is a method of using the idea of fast scheduling .

Fast scheduling each round is to divide a set of data into three parts , A number less than the reference number , Benchmark number , A number greater than or equal to the reference number . It is conceivable that when the number greater than or equal to the reference number is equal to K This part is the answer . We can use the idea of fast descending sorting , Because the fast platoon will determine the final position of a reference number at a time , Get the subscript of the reference number every time （ Subscript from 0 Start ） Then we'll compare it with k-1 Compare , When equal to , Explain that the reference number and the number to the left of the reference number are the first K Large number （ Note that these numbers are not in descending order ）. When less than , It indicates that the datum and the number on the left are not enough K individual , However, it can be determined that the reference number and the number to the left of the reference number must be here K In number , So don't worry about the benchmark number and the number on his left , Repeat the above operation for the number on the right , Until you get the answer . When greater than , Indicates that the reference number and the number to the left of the reference number are more than k individual , Do the above operation for the number on the left , Until you get the answer . The average time complexity is twice as fast as that of fast queue O（nlogn), The worst time complexity is O(n^2).

Code

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>

using namespace std;

void Qs(int low,int high,vector<int>&nums,int k)
{
    
	int i=low,j=high,temp=nums[low];
	while(i<j){
    
		while(i<j&&nums[j]<temp){
    
			j--;
		}
		nums[i]=nums[j];
		while(i<j&&nums[i]>=temp){
    
			i++;
		}
		nums[j]=nums[i];
	}
	nums[i]=temp;
	if(j==k-1){
    
		return ;
	}else{
    
		if(j>=k){
    
			Qs(low,j-1,nums,k);
		}else{
    
			Qs(i+1,high,nums,k);
		}
	}
}

int main()
{
    
	int n,k,x;
	vector<int>nums;
	nums.clear();
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++){
    
		scanf("%d",&x);
		nums.push_back(x);
	}
	Qs(0,n-1,nums,k);
	for(int i=0;i<k;i++){
    
		if(i!=0){
    
			printf(" "); 
		}
		printf("%d",nums[i]);
	}
	return 0;
}