描述
给定一个数组包含n个元素，统计前m大的数并且把这m个数从大到小输出。
输入
第一行包含一个整数n，表示数组的大小。n < 100000。
第二行包含n个整数，表示数组的元素，整数之间以一个空格分开。每个整数的绝对值不超过100000000。
第三行包含一个整数m。m < n。
输出
从大到小输出前m大的数，每个数一行
排序后再输出，复杂度 O(nlogn)
用分治处理：复杂度 O(n+mlogm)
思路
把前m大的都弄到数组最右边，然后对这最右边m个元素排序，再输出
引入操作 arrangeRight(k): 把数组(或数组的一部分）前k大的
都弄到最右边
一：
如何将前k大的都弄到最右边
1）设key=a[0], 将key挪到适当位置，使得比key小的元素都在
key左边，比key大的元素都在key右边（线性时间完成）
2) 选择数组的前部或后部再进行 arrangeRight操作
二：
- 选择数组的前部或后部再进行 arrangeRight操作
a = k done
a > k 对最右边a-1个元素再进行arrangeRigth(k)
a < k 对左边b个元素再进行arrangeRight(k-a)
关键
O(n)时间内实现把前m大的都弄到数组最右边
将前m大的都弄到数组最右边的时间：
T(n) = T(n/2) + a
n
= T(n/4) + a
n/2 + a
n
= T(n/8) + a
n/4 + a
n/2 + a
n
= …
= T(1) + … + a
n/8 + a
n/4 + a
n/2 + a
n
< 2
a
n
即 O(n)
以上思路来自北大郭伟老师
代码
#include<iostream>
#include<algorithm>
using namespace std;
#define N 10000+5
int a[N];
int b[N];
int n, m;
bool compare(int x, int y) {
return x > y;
}
void arrangeRight(int L, int R) {
int j = L+1;
for(int i = L+1; i <= R; i++) {
if(a[i] < a[L]) {
swap(a[i], a[j]);
j++;
}
}
j--;
swap(a[j], a[L]);
if(n - j == m) return;
else if(n - j < m) arrangeRight(L, j-1);
else if(n - j > m) arrangeRight(j+1, R);
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
arrangeRight(0, n-1);
int count = 0;
for(int i = n - m; i < n; i++) b[count++] = a[i];
sort(b, b+m, compare);
for(int i = 0; i < m; i++) printf("%d ", b[i]);
return 0;
}