n个数里找出前m个数（m<<n）
引子
每年十一月各大IT公司都不约而同、争后恐后地到各大高校进行全国巡回招聘。与此同时，网上也开始出现大量笔试面试题；网上流传的题目往往都很精巧，既能让考查基础知识，又在平淡中隐含了广阔的天地供优秀学生驰骋。
从10亿个浮点数中找出最大的1万个。
这是一道似易实难的题目，一般同学最容易中的陷阱就是没有重视这个“亿”字。因为有10亿个单精度浮点数元素的数组在32位平台上已经达到3.7GB之巨，在常见计算机平台（如Win32）上声明一个这样的数组将导致堆栈溢出。正确的解决方法是分治法，比如每次处理100万个数，然后再综合起来。不过这不是本文要讨论的主旨，所以本文把上题的10亿改为1亿，把浮点数改为整数，这样可以直接地完成这个问题，有利于清晰地讨论相关算法的优化
不假思索
拿到这道题，马上就会想到的方法是建立一个数组把1亿个数装起来，然后用for循环遍历这个数组，找出最大的1万个数来。原因很简单，因为如果要找出最大的那个数，就是这样解决的；而找最大的1万个数，只是重复1万遍而已。
也就相当于局部的选择排序.
代码
//局部选择排序 将长度为size的数组中的最大的前num个数字排好。
void selectsort(int data[],size_t size,size_t num){
for(size_t i=0;i<num;i++){
size_t max=i;
for(size_t j=i+1;j<size;j++){
if(data[j]>data[max]){
max=j;
}
}
if(max!=i){
int temp=data[i];
data[i]=data[max];
data[max]=temp;
}
}
}
略微动点脑子：
其实从我们仔细分析该算法的运算效率就可以发现,该算法的时间复杂度是O(m*n)这里就是1万*1亿 即 一万亿
而快速排序的时间复杂度是O(n*logn) 也就是1亿*logn 大概是30亿。
所以我们可以通过先快速排序把1亿个数排好然后取前10000个。效率要比局部选择排序还要快得多。也就是说这里只要满足O(n*logn)<O(n*m)即 logn<m 就满足快速排序比局部的选择排序要快。(log 100000000<m 即m>30).
进一步分析
我们考虑用快速排序解决问题是因为 快排的的n*对数级效率那么还有没有其他的对数级效率的排序呢?答案是有的例如我们学习到的排序二叉树，当然我们自己去实现一颗这样的树太费劲。不用担心，其实我们的C++提高的标准模板库中已经有了几个非常高效率的自平衡的二叉树 set map multimap multiset
在这里我们就用set来分析一下。
不用考虑太多我们只需要把数据一个个的灌入set中就可以了，最后遍历前10000个也行。
这个算法的时间复杂度也是n*logn
不过我们不用把一亿个数全部进入到set中，就维持10000个就好了多的比较一下比最小的删掉。这样的效率就可以提高到。n*logm 也就是log10000（因为我们只需要维护一个10000个元素大小的set空间就可以了）不过这样也并没有相对于快速排序提高多少性能，别看m远小于n就以为logm远小于logn 其实log100000000 也就是log10000的两倍而已。
set<int> oset;
int msize=10000;
void push_max(T t){ //擂台算法
if(size<msize){
tcout++;
oset.insert(t);
size++;
if(t<min)
min=t;
}else{
oset.insert(t); //logm 也就是log10000 大概就是15
oset.erase(*oset.begin()); //logm 也就是log10000 大概就是15
min=*(oset.begin());
}
那么从这里来看的话该算法的运算速度也不过是比快速排序快了一倍而已。
深思熟虑
那么还有没有更快的方法呢？进过分析以上的程序我们可以发现每次我们都只需要把set中的最小值比较一下就可以过滤掉大部分的数据，所以我设计了如下的擂台算法。思路就是创建一个新的容器
该容器记录一个最小值和容器的最大容量（m）容器最小值其实就是容器中的set树的最左节点也就是如下的oset.begin()的值。
经过测试一下程序的运算效率可以达到快速排序的30倍 也就是
而且还发现一个有趣的现象在排序的过程中，set中一直都保存着已经遍历的的数据的前m个最大值。
int tcout=0;//用来测试进入到操作树的次数
template<class T>
class Tset{
private:
size_t msize;//最大容量
public:
set<T> oset;
size_t size;//数量
T min;//最小值
T max;//最大值
Tset(size_t msize):msize(msize),size(0){}
Tset(){}
~Tset(){
}
void push_max(T t){ //擂台算法
if(size<msize){
tcout++;
oset.insert(t);
size++;
if(t<min)
min=t;
}else{
if(t>min){ //把比第m个最小的数个过滤掉了 不需要进入到调整set中
tcout++;
oset.insert(t); //logm 也就是log10000 大概就是15
oset.erase(min); //logm 也就是log10000 大概就是15
min=*(oset.begin());
}
}
if(t>max){
max=t;
}
}
};
这个算法的时间复杂度接近于O(n) 在这里也就是接近1亿次的运算 几乎只要把每一个数扫描一次就可以取出一亿个数中的前一万个。
全部代码：
//局部排序 从n个无序的数中选出前 m个数 如从一百万个无序数列中选出最大的1000个数
#include<iostream>
#include<set>
#include<string>
#include<ctime>
#include<cstdlib>
using namespace std;
int tcout=0;//用来测试进入到操作树的次数
template<class T>
class Tset{
private:
size_t msize;//最大容量
public:
set<T> oset;
size_t size;//数量
T min;//最小值
T max;//最大值
Tset(size_t msize):msize(msize),size(0){}
Tset(){}
~Tset(){
}
void push_max(T t){
if(size<msize){
tcout++;
oset.insert(t);
size++;
if(t<min)
min=t;
}else{
if(t>min){
tcout++;
oset.insert(t);
oset.erase(min);
min=*(oset.begin());
}
}
if(t>max){
max=t;
}
}
void print(){
for(set<int>::iterator it=oset.begin();it!=oset.end();){
int i=0;
for(;i<8&&it!=oset.end();i++){
cout<<*it<<' ';
it++;
}
cout<<endl;
}
}
};
int main(){
srand(time(0));
int arr[1000000]={0};
for(int i=0;i<1000000;i++){
arr[i]=rand()%10000000;
}
int n=1000;
//存储前n最大数
Tset<int> tst(n);
for(int i=0;i<1000000;i++){
tst.push_max(arr[i]);
}
tst.print();
cout<<"计算次数："<<tcout<<endl;
return 0;
}