Mr Loser

题解 P1177 【【模板】快速排序】

2019-06-30 08:54:10


本人专业研究非递归版算法五百年。。。

虽说归并是本题的正解之一,但是蒟蒻的归并跑了600多ms,令蒟蒻很不满意。于是本人瞎敲出了一个非递归版的归并,并且只跑了135ms,可以说是比较快了(相对递归版归并)。

代码和注释都在下面:

#include<cstdio>
using namespace std;

int temp[1000000];  //10倍数组空间
void merge(int a[],int l,int r,int mid){    //归并的合并程序段
    int k=l,m=mid+1,n=l;
    while(k<=mid&&m<=r){
        if(a[k]>a[m]){temp[n]=a[m];m++;n++;}
        else if(a[k]<=a[m]){temp[n]=a[k];k++;n++;}
    }
    while(k<=mid){temp[n]=a[k];k++;n++;}
    while(m<=r){temp[n]=a[m];m++;n++;}
    for(int n=l;n<=r;n++){a[n]=temp[n];}
}
void sort(int a[],int size){
    int i=2;    //长度从2开始,因为无法合并长度和为1的两个区间
    for(;i<size;i<<=1){ //长度循环
        int j=0;    //数组下标从0开始
        for(;j+i<=size;j+=i){   //归并区间循环(之所以使用j+i<=n作为循环条件,是因为我们要考虑到剩余的区间,别让它们太孤独)
            merge(a,j,j+i-1,j+(i>>1)-1);    //合并
        }
        merge(a,j,size-1,j+(i>>1)-1);   //合并剩余的区间
    }
    merge(a,0,size-1,(i>>1)-1); //合并最后剩下的两个区间
}

int a[1000000],n;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    sort(a,n);
    for(int i=0;i<n;i++){
        printf("%d ",a[i]);
    }
}