核心代码

getrand

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <string.h>
#define MAXN 1000006
using namespace std;
char filename[13][128];
char tmp1[]="./data/randnum-";
char tmp2[]=".txt";
char tmp3[10]="100";
char tmp4[]="-rand",tmp5[]="-increase";

//int n,m,t;
int m=66666666;
//t=0 随机取值 t=1顺序递增 t=2顺序递减
int a[MAXN];
bool cmp(int a,int b){
    return b<a;
}
int main(){
    for(int i=1;i<=10;i++){
        strcpy(filename[i],tmp1);
    }
    for(int i=1;i<=5;i++){
        strcat(filename[i],tmp3);
        strcat(filename[i],tmp4);
        strcat(filename[i],tmp2);
        strcat(filename[i+5],tmp3);
        strcat(filename[i+5],tmp5);
        strcat(filename[i+5],tmp2);
        tmp3[i+2]='0';
        tmp3[i+3]='\0';
    }

    srand(time(NULL));
    int tmp=100;
    for(int i=1;i<=5;i++){
        ofstream fout1(filename[i]);
        ofstream fout2(filename[i+5]);
        //fout1<<tmp<<endl;fout2<<tmp<<endl;
        for(int i=1;i<=tmp;i++)a[i]=(double)rand()/RAND_MAX * (m)+1;
        for(int i=1;i<=tmp;i++)fout1<<a[i]<<" ";
        sort(a,a+tmp);
        for(int i=1;i<=tmp;i++)fout2<<a[i]<<" ";
        fout1.close();fout2.close();
        tmp*=10;
    }
    return 0;
}

mergesort

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <cmath>
#include <string.h>
using namespace std;
#define MAXN 1000006
//归并排序
char filename[13][128];
char tmp1[]="./data/randnum-";
char tmp2[]=".txt";
char tmp3[10]="100";
char tmp4[]="-rand",tmp5[]="-increase";

int n;
int a[MAXN],b[MAXN];
void merge(int arr[],int left,int mid,int right,int tmp[]){
    int i=left;
    int j=mid+1;
    int t = 0;
    while (i<=mid && j<=right){
        if (arr[i]<=arr[j]){
            tmp[t++]=arr[i++];
        }else{
            tmp[t++]=arr[j++];
        }
    }
    while(i<=mid)tmp[t++]=arr[i++];
    while(j<=right)tmp[t++]=arr[j++];
    t=0;
    while(left<=right)arr[left++]=tmp[t++];

}
void mergesort(int arr[],int left,int right,int tmp[]){
    if (left<right){
        int mid=(left+right)/2;
        mergesort(arr,left,mid,tmp);
        mergesort(arr,mid+1,right,tmp);
        merge(arr,left,mid,right,tmp);
    }

}

int main(){
    clock_t start, stop;
    cout<<"This is the test for Merge-sort algorithm:"<<endl;
    for(int i=1;i<=10;i++)strcpy(filename[i],tmp1);
    for(int i=1;i<=5;i++){
        strcat(filename[i],tmp3);
        strcat(filename[i],tmp4);
        strcat(filename[i],tmp2);
        strcat(filename[i+5],tmp3);
        strcat(filename[i+5],tmp5);
        strcat(filename[i+5],tmp2);
        tmp3[i+2]='0';
        tmp3[i+3]='\0';
    }
    cout<<"Task:random 1e2,1e3,1e4,1e5,1e6, get 0.5N big num:"<<endl;
    int tmp=100;
    for(int i=1;i<=5;i++){
        ifstream fin(filename[i]);
        for(int j=0;j<tmp;j++)fin>>a[j];
        start=clock();
        mergesort(a,0,tmp-1,b);
        cout<<"0.5N: "<<a[tmp/2];
        stop=clock();
        cout<<" Scale: "<<tmp<<" Time: "<<1000*((double) (stop - start) / CLOCKS_PER_SEC)<<"ms"<<endl;
        fin.close();
        tmp*=10;
    }

    return 0;
}

randselect

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <string.h>
#define MAXN 1000006
using namespace std;
char filename[13][128];
char tmp1[]="./data/randnum-";
char tmp2[]=".txt";
char tmp3[10]="100";
char tmp4[]="-rand",tmp5[]="-increase";
int a[MAXN];

void swap(int *m, int *n){
    int tmp;tmp= *m;*m = *n;*n = tmp;
}
int partition(int l,int r){
    int x=a[r];
    int i=l-1;
    for(int j=l;j<r;j++){
        if(a[j]<=x){
            i++;
            swap(&a[i],&a[j]);
        }
    }
    swap(&a[i+1],&a[r]);
    return i+1;
}
int random_partition(int l, int r){
    int t=l+rand() % (r-l+1);
    swap(&a[t],&a[r]);
    return partition(l,r);
}
int random_select(int l,int r,int num){
    if(l==r)return a[l];
    int pivot=random_partition(l,r);
    int k=pivot-l+1;
    if(num==k)return a[pivot];
    else if(num<k)return random_select(l,pivot-1,num);
    else return random_select(pivot+1,r,num-k);
}
int main(){
    cout<<"This is the test for rand-select algorithm:"<<endl;
    srand(time(NULL));
    clock_t start, stop;
    for(int i=1;i<=10;i++)strcpy(filename[i],tmp1);
    for(int i=1;i<=5;i++){
        strcat(filename[i],tmp3);
        strcat(filename[i],tmp4);
        strcat(filename[i],tmp2);
        strcat(filename[i+5],tmp3);
        strcat(filename[i+5],tmp5);
        strcat(filename[i+5],tmp2);
        tmp3[i+2]='0';
        tmp3[i+3]='\0';
    }
    int tmp=100;
    cout<<"Task2:random 1e2,1e3,1e4,1e5,1e6, get 0.5N big num:"<<endl;
    for(int i=1;i<=5;i++){
        ifstream fin(filename[i]);
        for(int j=0;j<tmp;j++)fin>>a[j];
        start=clock();
        cout<<"0.5N: "<<random_select(0,tmp-1,tmp/2);
        stop=clock();
        cout<<" Scale: "<<tmp<<" Time: "<<1000*((double) (stop - start) / CLOCKS_PER_SEC)<<"ms"<<endl;
        fin.close();
        tmp*=10;
    }

    cout<<"Task3:random 1e6, get 0.2N,0.4N,0.6N,0.8N big num:"<<endl;
    tmp=1000000;
    ifstream fin1(filename[5]);
    for(int i=0;i<tmp;i++)fin1>>a[i];
    fin1.close();
    for(int i=1;i<=4;i++){
        start=clock();
        cout<<"0."<<(i*2)<<"N:"<<random_select(0,tmp-1,(tmp/5)*i)<<" ";
        stop=clock();
        cout<<"Time: "<<1000*((double) (stop - start) / CLOCKS_PER_SEC)<<"ms"<<endl;
    }
    cout<<"Task4:increase 1e2,1e3,1e4,1e5,1e6, get 0.5N big num:"<<endl;
    tmp=100;
    for(int i=1;i<=5;i++){
        ifstream fin(filename[i+5]);
        for(int j=0;j<tmp;j++)fin>>a[j];
        start=clock();
        cout<<"0.5N: "<<random_select(0,tmp-1,tmp/2);
        stop=clock();
        cout<<" Scale: "<<tmp<<" Time: "<<1000*((double) (stop - start) / CLOCKS_PER_SEC)<<"ms"<<endl;
        fin.close();
        tmp*=10;
    }
    return 0;
}

select

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <cmath>
#include <string.h>
#define MAXN 1000006
using namespace std;
struct PACK{int index,value;};
int a[MAXN];
char filename[13][128];
char tmp1[]="./data/randnum-";
char tmp2[]=".txt";
char tmp3[10]="100";
char tmp4[]="-rand",tmp5[]="-increase";
void swap(int *m, int *n);

int partition(int l,int r,int pivot){
    int tmp=a[pivot];
    int i=l-1;
    for(int j=l;j<=r;j++){
        if(a[j]<=tmp){
            i++;swap(&a[i], &a[j]);
        }
    }
    swap(&a[i],&a[pivot]);
    return i;
}
void insert_sort(int a[],int l, int r){
    int key,j;
    for(int i=l;i<=r;i++){
        key=a[i];
        j=i-1;
        while(j>=l && a[j]>key){
            a[j+1]=a[j];j--;
        }
        a[j+1]=key;
    }
}
PACK select(int l,int r,int num){
    if(r-l<=4){
        insert_sort(a,l,r);
        PACK pack1;
        pack1.index=l+num-1;
        pack1.value=a[pack1.index];
        return pack1;
    }
    if(r-l<140){
        insert_sort(a,l,r);
        PACK pack1;
        pack1.index=l+num-1;
        pack1.value=a[l+num-1];
        return pack1;
    }
    for(int i=0;i*5<=(r-l);i++){
        if(l+i*5+4>r){
            insert_sort(a,l+i*5,r);
            int mid=l+i*5+(r-(l+i*5))/2;
            swap(&a[mid],&a[l+i]);
        }else{
            insert_sort(a,l+i*5,l+i*5+4);
            int mid=l+i*5+2;
            swap(&a[mid],&a[l+i]);
        }
    }
    PACK pack2=select(l,l+(r-l)/5,((r-l)/5+1)/2);
    int pivot=partition(l,r,pack2.index);
    int k=pivot-l+1;
    if(num==k) {
        PACK pack3;
        pack3.index=pivot;pack3.value=a[pivot];
        return pack3;
    }else if(num<k)return select(l,pivot-1,num);
    else return select(pivot+1,r,num-k);
}

int main(){
    cout<<"This is the test for SELECT algorithm:"<<endl;
    srand(time(NULL));
    clock_t start, stop;
    for(int i=1;i<=10;i++)strcpy(filename[i],tmp1);
    for(int i=1;i<=5;i++){
        strcat(filename[i],tmp3);
        strcat(filename[i],tmp4);
        strcat(filename[i],tmp2);
        strcat(filename[i+5],tmp3);
        strcat(filename[i+5],tmp5);
        strcat(filename[i+5],tmp2);
        tmp3[i+2]='0';
        tmp3[i+3]='\0';
    }
    int tmp=100;
    cout<<"Task2:random 1e2,1e3,1e4,1e5,1e6, get 0.5N big num:"<<endl;
    for(int i=1;i<=5;i++){
        ifstream fin(filename[i]);
        for(int j=0;j<tmp;j++)fin>>a[j];
        start=clock();
        cout<<"0.5N: "<<select(0,tmp-1,tmp/2).value;
        stop=clock();
        cout<<" Scale: "<<tmp<<" Time: "<<1000*((double) (stop - start) / CLOCKS_PER_SEC)<<"ms"<<endl;
        fin.close();
        tmp*=10;
    }

    cout<<"Task3:random 1e6, get 0.2N,0.4N,0.6N,0.8N big num:"<<endl;
    tmp=1000000;
    ifstream fin1(filename[5]);
    for(int i=0;i<tmp;i++)fin1>>a[i];
    fin1.close();
    for(int i=1;i<=4;i++){
        start=clock();
        cout<<"0."<<(i*2)<<"N:"<<select(0,tmp-1,(tmp/5)*i).value<<" ";
        stop=clock();
        cout<<"Time: "<<1000*((double) (stop-start)/ CLOCKS_PER_SEC)<<"ms"<<endl;
    }


    cout<<"Task4:increase 1e2,1e3,1e4,1e5,1e6, get 0.5N big num:"<<endl;
    tmp=100;
    for(int i=1;i<=5;i++){
        ifstream fin(filename[i+5]);
        for(int j=0;j<tmp;j++)fin>>a[j];
        start=clock();
        cout<<"0.5N: "<<select(0,tmp-1,tmp/2).value;
        stop=clock();
        cout<<" Scale: "<<tmp<<" Time: "<<1000*((double) (stop-start)/ CLOCKS_PER_SEC)<<"ms"<<endl;
        fin.close();
        tmp*=10;
    }


    return 0;
}
void swap(int *m, int *n){
    int tmp;tmp= *m;*m = *n;*n = tmp;
}

oj1

#include<iostream>
#include<fstream>
#include<cstdlib>
#include<ctime>
using namespace std;
int a[4500006];
int n,i;
void swap(int *m, int *n){
    int tmp;
    tmp = *m;
    *m = *n;
    *n = tmp;
}
int partition(int p, int r){
    int x = a[r];
    int i = p-1;
    for(int j = p;j < r; j++){
        if(a[j] <= x){
            i = i + 1;
            swap(&a[i], &a[j]);
        }
    }
    swap(&a[i+1], &a[r]);
    return i + 1;
}
int random_partition(int p, int r){
    int t = p + rand() % (r - p + 1);
    swap(&a[t], &a[r]);
    return partition(p, r);
}
int random_select(int p, int r, int i){
    if(p == r) return a[p];
    int pivot = random_partition(p, r);
    int k = pivot - p + 1;
    if(i == k) return a[pivot];
    else if(i < k) return random_select(p, pivot - 1, i);
    else return random_select(pivot + 1, r, i - k);
}
int main(){
    srand(time(NULL));

    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    cout<<random_select(0,n-1,n/2)<<endl;

    return 0;
}

oj2

#include<iostream>
#include<fstream>
#include<cstdlib>
#include<ctime>
using namespace std;
int a[4500006];
int n, i;
struct I2D{
    int index;
    int value;
};
void swap(int *m, int *n){
    int tmp;
    tmp = *m;
    *m = *n;
    *n = tmp;
}
int partition(int p, int r, int pivot){
    int x = a[pivot];
    int i = p-1;
    for(int j = p;j <= r; j++){
        if(a[j] <= x){
            i = i + 1;
            swap(&a[i], &a[j]);
        }
    }
    swap(&a[i], &a[pivot]);
    return i;
}
void insert_sort(int l, int r){
    int key, j;
    for(int i = l; i <= r; i++){
        key = a[i];
        j = i - 1;
        while(j >= l && a[j] > key){
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}
I2D select(int p, int r, int i){
    if(r - p < 140){
        insert_sort(p, r);
        I2D pack;
        pack.index = p + i - 1;
        pack.value = a[p + i - 1];
        return pack;
    }
    for(int u = 0; u <= (r - p) / 5; u++){
        if(p + u * 5 + 4 > r){
            insert_sort(p + u * 5, r);
            int mid = p + 5 * u + (r - (p + 5 * u)) / 2;
            swap(&a[mid], &a[p + u]);
        }
        else{
            insert_sort(p + u * 5, p + u * 5 + 4);
            int mid = p + 5 * u + 2;
            swap(&a[mid], &a[p + u]);
        }
    }
    I2D tmpPack = select(p, p + (r - p) / 5, ((r - p) / 5 + 1) / 2);
    int tmp = tmpPack.index;
    int pivot = partition(p, r, tmp);
    int k = pivot - p + 1;
    if(i == k) {
        I2D subPack;
        subPack.index = pivot;
        subPack.value = a[pivot];
        return subPack;
    }
    else if(i < k) return select(p, pivot - 1, i);
    else return select(pivot + 1, r, i - k);
}
int main(){
    srand(time(NULL));
    int n, i;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    I2D result = select(0, n-1, n/2);
    cout<<result.value<<endl;

    return 0;
}

result.txt

This is the test for rand-select algorithm:
Task2:random 1e2,1e3,1e4,1e5,1e6, get 0.5N big num:
0.5N: 25189978 Scale: 100 Time: 0ms
0.5N: 33041373 Scale: 1000 Time: 0ms
0.5N: 33370973 Scale: 10000 Time: 0ms
0.5N: 33265175 Scale: 100000 Time: 2ms
0.5N: 33328247 Scale: 1000000 Time: 12ms
Task3:random 1e6, get 0.2N,0.4N,0.6N,0.8N big num:
0.2N:13332520 Time: 14ms
0.4N:26632486 Time: 23ms
0.6N:40011801 Time: 27ms
0.8N:53340251 Time: 29ms
Task4:increase 1e2,1e3,1e4,1e5,1e6, get 0.5N big num:
0.5N: 25189978 Scale: 100 Time: 0ms
0.5N: 33041373 Scale: 1000 Time: 1ms
0.5N: 33370973 Scale: 10000 Time: 1ms
0.5N: 33265175 Scale: 100000 Time: 1ms
0.5N: 33328247 Scale: 1000000 Time: 49ms

This is the test for SELECT algorithm:
Task2:random 1e2,1e3,1e4,1e5,1e6, get 0.5N big num:
0.5N: 25189978 Scale: 100 Time: 1ms
0.5N: 33041373 Scale: 1000 Time: 0ms
0.5N: 33370973 Scale: 10000 Time: 2ms
0.5N: 33265175 Scale: 100000 Time: 5ms
0.5N: 33328247 Scale: 1000000 Time: 43ms
Task3:random 1e6, get 0.2N,0.4N,0.6N,0.8N big num:
0.2N:13332520 Time: 43ms
0.4N:26632486 Time: 36ms
0.6N:40011801 Time: 34ms
0.8N:53340251 Time: 37ms
Task4:increase 1e2,1e3,1e4,1e5,1e6, get 0.5N big num:
0.5N: 25189978 Scale: 100 Time: 0ms
0.5N: 33041373 Scale: 1000 Time: 0ms
0.5N: 33370973 Scale: 10000 Time: 0ms
0.5N: 33265175 Scale: 100000 Time: 2ms
0.5N: 33328247 Scale: 1000000 Time: 25ms