问题求解报告01

Kevin_K edited 6 年，2 月前

实验结果表：

注：净用时不计输入输出时间，所以规模较小时均显示为0.000。

算法\净用时(s)\数据规模 25 100 10000 1000000
插入排序 0.000 0.000 0.062 522.278
希尔排序 0.000 0.000 0.000 0.313
归并排序 0.000 0.000 0.015 1.875
快速排序 0.000 0.000 0.000 0.109
堆排序 0.000 0.000 0.000 0.237
基数排序 0.046 0.043 0.047 0.266

程序代码：

插入排序(C++ Code)：
#include <bits/stdc++.h>
using namespace std;
int a[1000000],t;
void insertionSorting(int n,int *p){
    for (int i=1;i<n;i++){
        int r=*(p+i),j=i-1;
        for (;j>=0;j--){
            if (*(p+j)>r){
                *(p+j+1)=*(p+j);
            }
            else{
                *(p+j+1)=r;
                break;
            }
        }
        if (j==-1){
            *p=r;
        }
    }
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    cin>>t;
    for (int i=0;i<t;i++){
        cin>>a[i];
    }
    clock_t start,finish;
    start=clock();
    insertionSorting(t,a);
    finish=clock();
    printf("cost:%.3lfs\n",(double)(finish-start)/CLOCKS_PER_SEC);
    for (int i=0;i<t;i++){
        cout<<a[i]<<endl;
    }
    fclose(stdin);
    fclose(stdout);
}
希尔排序(C++ Code)：
#include <bits/stdc++.h>
using namespace std;
int a[1000000],t;
void shellsSort(int n,int *p){
    for (int i=n/2;i;i/=2){
        for (int j=i;j<n;j++){
            int r=*(p+j),k=j-i;
            for (;k>=0;k-=i){
                if (*(p+k)>r){
                    *(p+k+i)=*(p+k);
                }
                else{
                    *(p+k+i)=r;
                    break;
                }
            }
            if (k<0&&k+i>=0){
                *(p+k+i)=r;
            }
        }
    }
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    cin>>t;
    for (int i=0;i<t;i++){
        cin>>a[i];
    }
    clock_t start,finish;
    start=clock();
    shellsSort(t,a);
    finish=clock();
    printf("cost:%.3lfs\n",(double)(finish-start)/CLOCKS_PER_SEC);
    for (int i=0;i<t;i++){
        cout<<a[i]<<endl;
    }
    fclose(stdin);
    fclose(stdout);
}
归并排序(C++ Code)：
#include <bits/stdc++.h>
using namespace std;
int a[1000000],t;
void mergeSort(int n,int *p){
    int s=1,i,j,l;
    while (s<n){
        i=0;
        while (i+s<n){
            j=i+s;
            l=min(n-i-s,s);
            vector<int> v;//其实可以引入一个与a数组等长的全局数组来优化效率，但我懒了……我忏悔。使用vector确实比较影响效率。
            for (int x=0,y=0;x<s||y<l;){
                if (x==s){
                    v.push_back(*(p+j+(y++)));
                }
                else if (y==l){
                    v.push_back(*(p+i+(x++)));
                }
                else if (*(p+i+x)<*(p+j+y)){
                    v.push_back(*(p+i+(x++)));
                }
                else{
                    v.push_back(*(p+j+(y++)));
                }
            }
            for (vector<int>::iterator q=v.begin();q!=v.end();q++){
                *(p+(i++))=*q;
            }
        }
        s*=2;
    }
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    cin>>t;
    for (int i=0;i<t;i++){
        cin>>a[i];
    }
    clock_t start,finish;
    start=clock();
    mergeSort(t,a);
    finish=clock();
    printf("cost:%.3lfs\n",(double)(finish-start)/CLOCKS_PER_SEC);
    for (int i=0;i<t;i++){
        cout<<a[i]<<endl;
    }
    fclose(stdin);
    fclose(stdout);
}
快速排序(C++ Code)：
#include <bits/stdc++.h>
using namespace std;
int a[1000000],t;
void quickSort(int n,int *p){
    int i=0,j=n-1,t=*p;
    if (n>1){
        while (i!=j){
            while (i<j&&*(p+j)>=t){
                j--;
            }
            if (i<j){
                *(p+(i++))=*(p+j);
            }
            while (i<j&&*(p+i)<=t){
                i++;
            }
            if (i<j){
                *(p+(j--))=*(p+i);
            }
        }
        *(p+i)=t;
        quickSort(i,p);
        quickSort(n-i-1,p+i+1);
    }
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    cin>>t;
    for (int i=0;i<t;i++){
        cin>>a[i];
    }
    clock_t start,finish;
    start=clock();
    quickSort(t,a);
    finish=clock();
    printf("cost:%.3lfs\n",(double)(finish-start)/CLOCKS_PER_SEC);
    for (int i=0;i<t;i++){
        cout<<a[i]<<endl;
    }
    fclose(stdin);
    fclose(stdout);
}
堆排序(C++ Code)：
#include <bits/stdc++.h>
using namespace std;
int a[1000000],t;
void heapSort(int n,int *p){
    int *q=new int[2*n];
    int x,y,v=n;
    for (int i=0;i<n;i++){
        q[i]=*(p+i);
        x=i;
        while (x&&q[x]<q[(x-1)/2]){
            swap(q[x],q[(x-1)/2]);
            x=(x-1)/2;
        }
    }
    for (int i=0;i<v;i++){
        *(p+i)=q[0];
        q[0]=q[--n];
        x=0;
        while (2*x<n){
            if (2*x+1==n){
                if (q[x]>q[2*x+1]){
                    swap(q[x],q[2*x+1]);
                }
                break;
            }
            if (q[x]<=q[2*x+1]&&q[x]<=q[2*x+2]){
                break;
            }
            y=2*x+(q[2*x+1]<q[2*x+2]?1:2);
            swap(q[x],q[y]);
            x=y;
        }
    }
    delete [] q;
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    cin>>t;
    for (int i=0;i<t;i++){
        cin>>a[i];
    }
    clock_t start,finish;
    start=clock();
    heapSort(t,a);
    finish=clock();
    printf("cost:%.3lfs\n",(double)(finish-start)/CLOCKS_PER_SEC);
    for (int i=0;i<t;i++){
        cout<<a[i]<<endl;
    }
    fclose(stdin);
    fclose(stdout);
}
基数排序(C++ Code)：
#include <bits/stdc++.h>
using namespace std;
int a[1000000],t,u[10][1000000],v[10];
int val(int x,int n){
    for (int i=0;i<n;i++){
        x/=10;
    }
    return x%10;
}
void radixSort(int n,int *p){
    for (int i=0;i<10;i++){
        memset(u,0,sizeof(u));
        memset(v,0,sizeof(v));
        for (int j=0;j<n;j++){
            u[val(*(p+j),i)][v[val(*(p+j),i)]++]=*(p+j);
        }
        int t=0;
        for (int j=0;j<10;j++){
            for (int k=0;k<v[j];k++){
                *(p+(t++))=u[j][k];
            }
        }
    }
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    cin>>t;
    for (int i=0;i<t;i++){
        cin>>a[i];
    }
    clock_t start,finish;
    start=clock();
    radixSort(t,a);
    finish=clock();
    printf("cost:%.3lfs\n",(double)(finish-start)/CLOCKS_PER_SEC);
    for (int i=0;i<t;i++){
        cout<<a[i]<<endl;
    }
    fclose(stdin);
    fclose(stdout);
}

附录:

比一般选择排序慢好多的选择排序(C++ Code)：
#include <bits/stdc++.h>
using namespace std;
int a[1000000],t;
void selectionSort(int n,int *p){
    for (int i=0;i<n;i++){
        for (int j=i+1;j<n;j++){
            if (*(p+i)>*(p+j)){
                swap(*(p+i),*(p+j));
            }
        }
    }
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    cin>>t;
    for (int i=0;i<t;i++){
        cin>>a[i];
    }
    clock_t start,finish;
    start=clock();
    selectionSort(t,a);
    finish=clock();
    printf("cost:%.3lfs\n",(double)(finish-start)/CLOCKS_PER_SEC);
    for (int i=0;i<t;i++){
        cout<<a[i]<<endl;
    }
    fclose(stdin);
    fclose(stdout);
}
内核为选择排序的负优化的假的希尔排序(C++ Code)：
#include <bits/stdc++.h>
using namespace std;
int a[1000000],t;
void falseShellsSort(int n,int *p){
    for (int i=n/2;i;i/=2){
        for (int j=0;j<i;j++){
            for (int k=0;j+k*i<n;k++){
                int o=k,m=*(p+j+k*i);
                for (int r=k+1;j+r*i<n;r++){
                    if (*(p+j+r*i)<m){
                        o=r;
                        m=*(p+j+r*i);
                    }
                }
                swap(*(p+j+k*i),*(p+j+o*i));
            }
        }
    }
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    cin>>t;
    for (int i=0;i<t;i++){
        cin>>a[i];
    }
    clock_t start,finish;
    start=clock();
    falseShellsSort(t,a);
    finish=clock();
    printf("cost:%.3lfs\n",(double)(finish-start)/CLOCKS_PER_SEC);
    for (int i=0;i<t;i++){
        cout<<a[i]<<endl;
    }
    fclose(stdin);
    fclose(stdout);
}

Comments

服务

首页 反馈 Polygon Wiki

开源

Github eJudge

关于我们

团队: @ultmaster, @zerol, @kblack.
联系方式: acmsupport@admin.ecnu.edu.cn