核心代码

实验数据

堆排序
1000 0ms
10000 1ms
100000 17ms
1000000 226ms
10000000 3816ms
nlgn
n*10 nlgn ->10nlg(10n)
快速排序
1000 0ms
10000 1ms
100000 9ms
1000000 112ms
10000000 1382ms

getrand

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
int s=0,t=100000000;
int main(){
    ofstream fout("data.txt");
    int n;
    srand(time(NULL));
    cin>>n;fout<<n;
    fout<<endl;
    int tmp;
    for(int i=1;i<=n;i++){
        tmp=((rand())*(rand()))%(t-s+1);
        fout<<tmp<<" ";
    }
    fout.close();
    return 0;
}

oj

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <time.h>
#include <stdlib.h>
using namespace std;
int a[1000000+6],n;

void heapify(int a[],int i,int n){
    int tmp,tmp1;
    if((2*i <= n ) && (a[2*i]>a[i]))tmp=2*i;
    else tmp=i;

    if((2*i+1<= n) &&  (a[2*i+1]>a[tmp]))tmp=2*i+1;

    if(tmp!=i){
        tmp1=a[i];a[i]=a[tmp];a[tmp]=tmp1;
        heapify(a,tmp,n);
    }
}
void buildheap(int a[],int n){
    for(int i=(n/2);i>=1;i--)heapify(a,i,n);
}
void heapsort(int a[],int n){
    buildheap(a,n);
    int tmp,tmplen=n,cnt=1;
    for(int i=n;i>=2;i--){
        int tmp=a[1];a[1]=a[i];a[i]=tmp;
        --tmplen;++cnt;
        heapify(a,1,tmplen);
    }
    return;
}
int main(){

    cin>>n;for(int i=1;i<=n;i++)cin>>a[i];;
    heapsort(a,n);
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    return 0;
}

priorityqueue

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <time.h>
using namespace std;
int a[10000000+6],n;

void heapify(int a[],int i,int n){
    int tmp,tmp1;
    if((2*i<=n) && (a[2*i]>a[i]))tmp=2*i;
    else tmp=i;

    if((2*i+1<= n) &&  (a[2*i+1]>a[tmp]))tmp=2*i+1;

    if(tmp!=i){
        tmp1=a[i];a[i]=a[tmp];a[tmp]=tmp1;
        heapify(a,tmp,n);
    }
}
void buildheap(int a[],int n){
    for(int i=(n/2);i>=1;i--)heapify(a,i,n);
}
void heapsort(int a[],int n){
    buildheap(a,n);
    int tmp,tmplen=n,cnt=1;
    for(int i=n;i>=2;i--){
        int tmp=a[1];a[1]=a[i];a[i]=tmp;
        --tmplen;++cnt;
        heapify(a,1,tmplen);
    }
    return;
}
int main(){
    ifstream fin("data.txt");
    ofstream fout("result.txt");
    fin>>n;for(int i=1;i<=n;i++)fin>>a[i];
    clock_t start,stop;
    start=clock();
    heapsort(a,n);
    stop=clock();
    for(int i=1;i<=n;i++)fout<<a[i]<<" ";
    cout<<"Time:"<<1000*(((double) (stop - start))/CLOCKS_PER_SEC)<<"ms"<<endl;
    fin.close();
    fout.close();
    return 0;
}

quicksort

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <time.h>
using namespace std;
int a[10000000+6],n;
int partition(int a[],int left,int right){
    int tmp=a[right];
    int i=left-1;
    int tmp1;
    for(int j=left;j<right;j++){
        if(a[j]<=tmp){
            ++i;
            tmp1=a[i];a[i]=a[j];a[j]=tmp1;
        }
    }
    tmp1=a[i+1];a[i+1]=a[right];a[right]=tmp1;
    return 1+i;
}
void quicksort(int a[],int left,int right){
    if(left<right){
        int mid=partition(a,left,right);
        quicksort(a,left,mid-1);
        quicksort(a,mid+1,right);
    }
}
int main(){
    ifstream fin("data.txt");
    ofstream fout("result.txt");
    fin>>n;for(int i=0;i<n;i++)fin>>a[i];
    clock_t start,stop;
    start=clock();
    quicksort(a,0,n-1);
    stop=clock();
    for(int i=0;i<n;i++)fout<<a[i]<<" ";
    cout<<"Time:"<<1000*(((double) (stop - start))/CLOCKS_PER_SEC)<<"ms"<<endl;
    fin.close();
    fout.close();
    return 0;
}