优雅的归并排序代码

作者: admin
标签: 分而治之
更新: 8/8/2019, 10:46:43 PM
#include <cstdio>
void merge( int h, 
            int m, 
            int* left, 
            int* right, 
            int *array){//合并两个数组
    int i = 0, j = 0,k =0;
    while(i<h&&j<m){
        if(left[i]<right[j]){
            array[k] = left[k];
            i++;
        } else {
            array[k] = right[k];
            j++;
        }
        k++;
    }
    if(i==h){
        for(int t=i;t<m;t++)
            array[k+t] = right[t];
    } else {
        for(int t=j;t<h;t++)
            array[k+t] = left[t];
    }
}


void mergesort(int n, int *array){//归并排序
    if(n>1){
        int h = n>>1, m = n - h;
        int left[h], right[m];
        for(int i=0;i<h;i++) left[i] = array[i];
        for(int i=0;i<m;i++) right[i] = array[h+i];
        mergesort(h, left);
        mergesort(m, right);
        merge(h, m, left, right, array);
    }
}
int main(int argc, char const *argv[])
{
    int s[100];
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&s[i]);
    mergesort(n, s);
    for (int i = 0; i < n; ++i)
    {
        /* code */
        printf("%d ", s[i]);
    }
    return 0;
}
删除
修改
点击登陆评论