100 105 110 200
min         max
------------------
insert 99,omited
------------------
insert 106
106 105 110 200
    min     max
(min指针,即105之前已经为混乱区域,不能在这里插入,必须在min指针之后插入)
---------------
insert  201
106 201 110 200
    max min
--------------
insert 5,omited
-----------------
insert 112
106 201 112 200
    max     min
(到达尾部,排序)
------------------
106 112 200 201
min         max
--------------

#include <stdio.h>
#include <set>
#include <time.h>

int main( int argc, char *argv[] ) {
    std::set<float> A,B;
    std::set<float> *t;
    size_t count = 0;
    clock_t c = clock();
    FILE *fp = fopen( argv[1], "r+b" );
    // 取1w个数并排序
    while( !feof(fp) && A.size()<10000 ) {
        float f;
        fread( &f, sizeof(f), 1, fp );
        count++;
        A.insert( f );
    }
    float min = *A.begin();
    t = &A;
    // 取剩下的数进行插入
    while( !feof(fp) ) {
        float f;
        count++;
        fread( &f, sizeof(f), 1, fp );
        if ( f > min ) {
            if ( A.find( f ) != A.end() || B.find( f ) != B.end() ) {
                continue;
            }
            t->erase( t->begin() );
            if ( B.size() < A.size() ) {
                B.insert( f );
            } else {
                A.insert( f );
            }
            if ( *A.begin() > *B.begin() ) {                
                t = &B;
                min = *B.begin();
            } else {
                t = &A;
                min = *A.begin();
            }
        }
    }
    {
        // 合并两个表
        std::set<float>::iterator iter = B.begin();
        while( iter != B.end() ) {
            A.insert( *iter );
            iter++;
        }
    }
    c = clock() - c;
    fclose( fp );
    std::set<float>::iterator iter = A.begin();
    while( iter != A.end() ) {
        printf( "%e\n", *iter );
        iter++;
    }
    printf( "count:%d\ntime:%dms\n", A.size(), c );
    return 0;
}

void top10000(void)
{
    FileRelated f;
    Counter<int> lengthForReadFile;
    vector<double> vectorForRead(VECTOR_SIZE);
    list<double> listForInsert(VECTOR_SIZE);

/*used for create-file mode
    f.CreateFile();
*/    
/*used for only-read-file mode
    for(Counter<int> read;read.NotArrived(f.LENGTH);read.Count(VECTOR_SIZE))
        f.ReadFile(vectorForRead.begin(),VECTOR_SIZE);
    return;
*/
    f.ReadFile(vectorForRead.begin(),VECTOR_SIZE);
    lengthForReadFile.Count(VECTOR_SIZE);
    
//1stStep:
    copy(vectorForRead.begin(),vectorForRead.end(),listForInsert.begin()); 
//2ndStep:
    sort(vectorForRead.begin(),vectorForRead.end());
    list<double>::iterator minPtr=listForInsert.begin();
    list<double>::iterator maxPtr=listForInsert.end();
    --maxPtr;

while(lengthForReadFile.NotArrived(f.LENGTH))
{
//3rdStep:
    f.ReadFile(vectorForRead.begin(),VECTOR_SIZE);
    lengthForReadFile.Count(VECTOR_SIZE);
//4thStep:
    for(vector<double>::iterator iter=vectorForRead.begin();
        iter!=vectorForRead.end();
        ++iter)
    {
        if(minPtr==listForInsert.end())
            minPtr=listForInsert.begin();
        
        else if(*iter>=*maxPtr)
        {
            maxPtr=minPtr++;
            *maxPtr=*iter;
        }
        else if(*iter>*minPtr)
        {
            list<double>::iterator replacePtr=
                find_if(listForInsert.begin(),listForInsert.end(),
                    bind2nd(greater<double>(),*iter));
            listForInsert.insert(replacePtr,*iter);//before replacePtr
            listForInsert.erase(minPtr++);
        }
    }
}
//nthStep:
    copy(listForInsert.begin(),listForInsert.end(),ostream_iterator<double>(cout," "));
}

规模       创建文件       空跑文件       所用时间       实际时间(单位均为秒)
1e7           30(大概)       10         20                   10
5e7           118            54         62                   8
1e8           164(iso:app)55,51(空跑了2次)62               7-11
1e8(another file)251            104      118                 14

//
// File: top10000.cc
// Created by: cc <tireless-heart@163.com>
// Created on: Fri Feb 29 12:26:53 2008
//

#include "top10000.h"
#include <iostream>
#include "FileRelated.h"
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>
#include "Counter.h"

using namespace std;
const static int VECTOR_SIZE=10000;

void top10000(void)
{
    FileRelated f;
    Counter<int> lengthForReadFile;
    vector<double> vectorForRead(VECTOR_SIZE);
    list<double> listForInsert(VECTOR_SIZE);
//1stStep:
    f.ReadFile(vectorForRead.begin(),VECTOR_SIZE);
    lengthForReadFile.Count(VECTOR_SIZE);
    copy(vectorFor.begin(),vectorForRead.end(),listForInsert.begin()); 
//2ndStep:
    sort(vectorForInsert.begin(),vectorForInsert.end());
    list<double>::iterator minPtr=listForInsert.begin();
    list<double>::iterator maxPtr=listForInsert.end();
    --maxPtr;

    while(lengthForReadFile.NotArrived(f.LENGTH))
    {
//3rdStep:
        f.ReadFile(vectorForRead.begin(),VECTOR_SIZE);
        lengthForReadFile.Count(VECTOR_SIZE);
//4thStep:
        for(vector<double>::iterator iter=vectorForRead.begin();
            iter!=vectorForRead.end();
            ++iter)
        {
            if(*iter>=*maxPtr)
            {
                listForInsert.insert(listForInsert.end(),*iter);
                ++maxPtr;
                listForInsert.erase(minPtr++);
            }
            else if(*iter>*minPtr)//*minPtr<*iter<*maxPtr
            {
                list<double>::iterator replacePtr=
                    find_if(listForInsert.begin(),listForInsert.end(),
                        bind2nd(greater_equal<double>(),*iter));
                listForInsert.insert(replacePtr,*iter);//before replacePtr
                listForInsert.erase(minPtr++);
            }
        }
    }
//5thStep:
    copy(listForInsert.begin(),listForInsert.end(),ostream_iterator<double>(cout," "));
}

//
// File: top10000.cc
// Created by: cc <tireless-heart@163.com>
// Created on: Fri Feb 29 12:26:53 2008
//

#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include "top10000.h"
#include "Counter.h"
#include "FileRelated.h"

using namespace std;
const static int VECTOR_SIZE=10000;

void top10000(void)
{
    FileRelated f;
    Counter<int> lengthForReadFile;
    vector<double> vectorForRead(VECTOR_SIZE);
    list<double> listForInsert(VECTOR_SIZE);
//1stStep:
    f.ReadFile(vectorForRead.begin(),VECTOR_SIZE);
    lengthForReadFile.Count(VECTOR_SIZE);
    sort(vectorForRead.begin(),vectorForRead.end());
    copy(vectorForRead.begin(),vectorForRead.end(),listForInsert.begin()); 
//2ndStep:
    list<double>::iterator minPtr=listForInsert.begin();
    list<double>::iterator maxPtr=listForInsert.end();
    --maxPtr;//

    while(lengthForReadFile.NotArrived(f.LENGTH))
    {
//3rdStep:
        f.ReadFile(vectorForRead.begin(),VECTOR_SIZE);
        lengthForReadFile.Count(VECTOR_SIZE);
//4thStep:
        for(vector<double>::iterator iter=vectorForRead.begin();
            iter!=vectorForRead.end();
            ++iter)
        {
            if(*iter>=*maxPtr)
            {
                listForInsert.insert(listForInsert.end(),*iter);
                ++maxPtr;
                listForInsert.erase(minPtr++);
            }
            else if(*iter>*minPtr)//*minPtr<*iter<*maxPtr
            {
                list<double>::iterator replacePtr=
                    find_if(listForInsert.begin(),listForInsert.end(),
                        bind2nd(greater_equal<double>(),*iter));
                listForInsert.insert(replacePtr,*iter);//before replacePtr
                listForInsert.erase(minPtr++);
            }
        }
    }
//5thStep:
    copy(listForInsert.begin(),listForInsert.end(),ostream_iterator<double>(cout," "));
}

 public class FloatRadixSortItem : RadixSortItem
    ...{
        float value;
        public float Value
        ...{
            get
            ...{
                return value;
            }
        }

        public FloatRadixSortItem(float Value)
        ...{
            value = Value;
            if (value < 0)
            ...{
                IsNegative = true;
            }
            else
            ...{
                IsNegative = false;
            }


            Data = new byte[4];
            byte[] temp = BitConverter.GetBytes(value);
            uint bi3 = temp[3];
            bi3 <<= 8;
            bi3 += temp[2];
            bi3 <<= 8;
            bi3 += temp[1];
            bi3 <<= 8;
            bi3 += temp[0];

            if (value < 0)
            ...{
                bi3 = ~bi3;
            }
            
            uint bi1 = bi3 & 0x7F800000;
            Data[3] = (byte)(bi1 >> 23);
            bi1 = bi3 & 0x7FFFFF;
            

            Data[0] = (byte)(bi1 & 0xFF);
            bi1 >>= 8;
            Data[1] = (byte)(bi1 & 0xFF);
            bi1 >>= 8;
            Data[2] = (byte)(bi1 & 0xFF);
            DataLen = 4;

        }
        public override string ToString()
        ...{
            return value.ToString() + " " + Data[0].ToString("X2") 
                +" " + Data[1].ToString("X2") 
            +" " + Data[2].ToString("X2") 
            +" " + Data[3].ToString("X2");
        }

#include <vector>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cmath>
#include <windows.h>
using namespace std;

size_t M = 10000;
size_t N = 2;
size_t DATA_LENGTH=5*100*100*M;
size_t INNER_DATA_LENGTH=N*M;

bool read_data(ifstream& ifile, double* data,size_t length)
{
    ifile.read((char*)data,length);        
    return true;
}
bool read_data(double* data,size_t length)
{
    static int j=0; 
    if(j++)return true;
    for(size_t i=0; i<length; i++)
    {
        data[i] = rand();
    }
    return true;
}

bool createdata(ofstream& out)
{
    if(!out.is_open())
        return false;
    double* data = new double[N*M];
    for(size_t i=0; i<DATA_LENGTH/INNER_DATA_LENGTH;i++)
    {
            for(size_t i=0; i<INNER_DATA_LENGTH; i++)
            {
                data[i] = sin(rand())*rand();
            }
            out.write((char*)data,INNER_DATA_LENGTH*sizeof(double));
    }
    delete[] data;
    return true;
}

void solver(ifstream& ifile)
{    
    if(!ifile.is_open())
    {
        cerr<<"无法打开文件"<<endl;
        return;
    }
    //记录从数据文件读入的数据
    double* data=new double[N*M];
    
    //每次从data中取出M个最大的数放入这个数组中[M+index,M+index+M)，
    double* better_data=new double[N*M];    
    int index = 0;
    
    if(better_data==NULL||data==NULL)
    {
        cerr<<"内存不足"<<endl;
        delete[] data;delete[] better_data;
        return;
    }

    for(int i=0; i<DATA_LENGTH/INNER_DATA_LENGTH;i++)
    {        
        while(index<INNER_DATA_LENGTH)
        {
            read_data(ifile,data,INNER_DATA_LENGTH);    
            //read_data(data,INNER_DATA_LENGTH);
            nth_element(data,better_data+M,data+INNER_DATA_LENGTH,greater<double>());
            copy(data,data+M,better_data+index);
            index+=M;
        }
        nth_element(better_data,better_data+M,better_data+INNER_DATA_LENGTH,greater<double>());    
        index=M;
    }

    delete[] better_data;
    delete[] data;
}
int main(int argc, char* argv[])
{
    const char* fname="test.dat";
    //生成测试数据
    ofstream ofile(fname,ios::binary|ios::out);
    createdata(ofile);
    ofile.close();
    //求解问题
    ifstream ifile("test.dat",ios::binary|ios::in);
    ifile.seekg(0,ios_base::beg);
    DWORD start = GetTickCount();    
    solver(ifile);
    DWORD end = GetTickCount(); 
    cout<<end-start<<endl;    
    return 0;
}

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.IO;

namespace WindowsApplication14
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
            for (int a = 0; a < 65536; a++)
            {
                container[a] = new List<float>();
            }
        }

        /// <summary>
        /// 内存容器
        /// </summary>
        List<float>[] container = new List<float>[65536];
        
        /// <summary>
        /// 可以使用的内存容器最小索引
        /// </summary>
        uint containerIndex = 0;

        /// <summary>
        /// 构造数据文件
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void button1_Click(object sender, EventArgs e)
        {
            FileStream data=File.Create("d:\\data.float", 1024 * 1024 * 10);
            DateTime bt1 = DateTime.Now;
            Random random=new Random();
            for (int a = 0; a < 1000000000; a++)
            {
                double temp = random.NextDouble();
                int bi1 = random.Next(10000000);
                temp = temp * bi1;
                float rand = (float)temp;
                byte[] array = BitConverter.GetBytes(rand);
                data.Write(array,0,4);
            }
            data.Close();
            DateTime bt2 = DateTime.Now;
            this.Text=(bt2-bt1).ToString();
        }

        int addCount = 0;
        /// <summary>
        /// 将数据加入到容器
        /// </summary>
        /// <param name="value"></param>
        /// <param name="dataFrame"></param>
        void AddContainer(float value, uint dataFrame)
        {
            addCount++;

            uint index = dataFrame & 0x7FFF8000;//01111111 11111111 10000000 00000000
            index >>= 15;
            //以上获得8位指数和8位头尾数组成的索引
            if (index >= containerIndex)
            {
                container[(int)index].Add(value);
            }
            //每当添加的数据大于1000w时进行整理
            if (addCount > 10000000)
            {
                //计数器清零
                addCount = 0;

                //容器中数据量的合计
                int sumContainerCount = 0;

                for (int a = 65535; a >= 0; a--)
                {
                    sumContainerCount += container[a].Count;
                    if (sumContainerCount >= 10000)
                    {
                        //移动可以使用的容器索引,小于此索引的容器不可以使用
                        containerIndex = (uint)a;
                        break;
                    }
                }
                //清理不可以使用的容器,释放内存
                for (int a = 0; a < containerIndex; a++)
                {
                    container[a].Clear();
                }
            }


        }
        /// <summary>
        /// 合并数据整理输出
        /// </summary>
        /// <returns></returns>
        List<float> Retuen()
        {
            List<float> R = new List<float>();
            for (int a = 65535; a >= containerIndex; a--)
            {
                R.AddRange(container[a]);
            }
            //调用.Net内置排序器，其实就是快排
            R.Sort();
            //将顺序反转
            R.Reverse();
            //返回10000个最大的数
            return R.GetRange(0, 10000);
        }


        /// <summary>
        /// 计算获得1W个最大数
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void button2_Click(object sender, EventArgs e)
        {
            FileStream data = File.OpenRead("d:\\data.float");
            DateTime bt1 = DateTime.Now;
            byte[] array = new byte[4];
            while (data.Read(array, 0, 4) > 0)
            {
                //转换为一个整数结构
                uint bi1 = BitConverter.ToUInt32(array,0);
                //还原为浮点数
                float bf1 = BitConverter.ToSingle(array, 0);
                AddContainer(bf1, bi1);
            }

            data.Close();
            Retuen();


            DateTime bt2 = DateTime.Now;
            this.Text = (bt2 - bt1).ToString();
        }
    }
}