大数挑选.cpp

五种排序算法

#include <iostream>
#include<memory.h>
#include <algorithm>
#include <functional>
#define N 10000

void MaxK_1(int a[], int n, int result[], int k);
void MaxK_2(int *bigr,int bigarr_len, int *res,int n);
void my_nth_element(int low,int high,int key[],int n);
void MaxK(int *bigr,int bigarr_len, int *res,int n);



int main()
{
    int a[N],result[N],i,k[8]={1,10,100,1000,10000,100000,1000000,5000000};
    for(i=0;i<N;i++)
       a[i]=rand();
       a[3]=100;
    for(i=0;i<3;i++)
    {
        printf("最大的%d个数：\n",k[i]);
        MaxK_1(a,N,result,k[i]);
        for(int j=0;j<k[i];j++)
          std::cout<<result[k[i]]<<"   ";
        printf("\n");
    }

    return 0;
}

void MaxK_1(int bigr[],int bigarr_len,int res[],int n){
    memcpy(res,bigr,sizeof(int)*n);
    std::sort(res,res+n);
//    my_qsort(0,n,res);
    int mindex=0;
    int minzone=mindex;

    for(int i=n;i<bigarr_len;i++){
        if(res[mindex]<bigr[i])    {
            res[mindex]=bigr[i];
            if(mindex==minzone)
                minzone++;
            if(    minzone==n) minzone--;
            int l=700;
            if(minzone>=l){
                std::sort( res , res + l+1);
                std::merge(res, res +l+1, res + l+1, res + n, bigr);
                memcpy(res,bigr,sizeof(int)*n);
                mindex=minzone=0;
                continue;
            }
            mindex=minzone;
            for(int k=minzone-1;k>=0;k--){
                if(res[k]<res[mindex])
                    mindex=k;
            }
        }

    }
}
void MaxK_2(int *bigr,int bigarr_len, int *res,int n){
    my_nth_element(0, bigarr_len-1, bigr,bigarr_len-n);
    memcpy(res,bigr+bigarr_len-n,sizeof(int)*n);
}
void MaxK(int *bigr,int bigarr_len, int *res,int n){
     if(n<15000)
          MaxK_1(bigr,bigarr_len,res,n);
     else
        MaxK_2(bigr,bigarr_len,res,n);
}
void my_nth_element(int low,int high,int key[],int n)
{
     int i=low,j=high,mid=(i+j)>>1,tag=key[i];
     if(high-low+1<n){printf("ERROR");return;}
     if(i<j)
     {
            do
            {
              while(tag<key[j] && i<j) j--;
              if(i<j)
              {
                key[i]=key[j];
                i++;
                while(tag>=key[i] && i<j) i++;
                if(i<j)
                {
                  key[j]=key[i];
                  j--;
                }
              }
            }while(i<j);
            key[i]=tag;
            //if(i==n)return;
            if(i-low>n)
                my_nth_element(low,j-1,key,n);
            else if(i-low+1<n)
                my_nth_element(i+1,high,key,n-(i-low+1));
     }
}