开发者社区云计算文章正文

归并排序【模板】

2016-03-13 1407

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

模板直接见代码：

#include <iostream>
using namespace std;

const long M=999999999;

void Merge(int A[],long Left,long Middle,long Right)
{
    long n1=Middle-Left+1;
    long n2=Right-Middle;

    int *L = new int[n1+2]; //预留空间
    int *R = new int[n2+2];

    long i,k;
    //分成左右数组
    for(i=1;i<=n1;i++)
        L[i]=A[Left+i-1];
    for(i=1;i<=n2;i++)
        R[i]=A[Middle+i];

    L[n1+1]=M; //哨兵
    R[n2+1]=M;

    i=1;
    long j=1;
    for(k=Left;k<=Right;k++)
    {
        //如果某一边先抵达哨兵，另一边一定是小于的
        if(L[i]<=R[j])
            A[k]=L[i++];

        else
            A[k]=R[j++];
    }

    delete L,R;
}

void Merge_sort(int A[],long Left,long Right)
{
    long Middle;
    if(Left<Right)
    {
        Middle=(Left+Right)/2; 
        Merge_sort(A,Left,Middle);  // 二分分解左部分
        Merge_sort(A,Middle+1,Right); // 二分分解有部分
        Merge(A,Left,Middle,Right); //合并两部分
    }
}

int main() 
{
    int array[10] = {4,5,7,1,22,33,8,10,23,199};

    Merge_sort(array,0,9);

    for(int i=0;i<10;++i) {
        cout<<array[i]<<" ";
    }

    return 0; 
}