输出n个数中前m个大的数可以采用先排序在取前m个大的数，这个最好的时间复杂度为O(nlogn)。可以利用快排的思想加快时间复杂度，下面算法时间复杂度为O(n+mlogm)，若m<<n时，则时间复杂度约为O(n)。
#include<iostream>
using namespace std;
int a[100];
void swap(int &a, int &b)
{
int temp;
temp = b;
b = a;
a = temp;
}
void QuickSort(int a[], int s, int e, int m)
{
if (s >= e)
return;
int k = a[s];
int i = s, j = e;
while (i != j)
{
if (j > i && a[j] > k)
j--;
swap(a[i], a[j]);
if (j > i && a[i] < k)
i++;
swap(a[i], a[j]);
}
int b = (e - j) + 1; // 判断右边大的数有几个
if (m > b) // 若小于m个，在左边再取m-b个
QuickSort(a, s, i, m - b);
if (m < b) // 若大于m个，在右边再去m个
QuickSort(a, j + 1, e, m);
}
int main()
{
int m,n;
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> a[i];
QuickSort(a, 0, n - 1, m);
for (int i = n-1; i >= n-m; i--)
cout << a[i] << ' ';
cout << endl;
system("pause");
}
输出n个数中前m个大的数可以采用先排序在取前m个大的数，这个最好的时间复杂度为O(nlogn)。可
阅读背景：
分治1——输出前m个大的数
来源：互联网
分享到：
