信息学奥赛一本通T1235-输出前k大的数

解题思路:快速排序，优化前K个排序， 当K 小于S时只排前半部分即可

注意事项:输入输出用scanf和printf

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N];
void quick_sort(int l, int r,int k){
	if(l >= r) return;
	int i = l - 1, j = r + 1, x = a[(l + r) >> 1];
	while(i < j){
		while(a[++i] > x);
		while(a[--j] < x);
		if(i < j) swap(a[i],a[j]);
	}
	int s = j - l + 1;
	quick_sort(l, j, k);
	if(k > s) quick_sort(j+1,r,k - s);
	return;	
}
int main()
{
	int k,n;
	cin >> n;
	for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
	cin >> k;
	quick_sort(0, n - 1,k);
	for(int i = 0; i < k; i ++) printf("%d\n",a[i]);

	return 0;
}