问题求解报告01

Kevin_K edited 5 年,5 月前

实验结果表:

注:净用时不计输入输出时间,所以规模较小时均显示为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