归并排序

简单分治之归并排序

分治模式，在每层递归有三个步骤：
分解：将原问题分解为若干子问题
解决：递归求解各子问题；当子问题的规模足够小时，则直接求解
合并：合并子问题的解成为原问题的解

#include <iostream>
#define MAX 0x7fffffff //用作哨兵
/*归并排序*/

//辅助子程序
//左右两个有序数组合并，时间复杂度o(n)
//参数描述
//a为当前要排序数组指针
//[p,q],[q+1,r]是数组的左右两部分，分别已是有序
void merge(int a[], int p, int q, int r)
{
    //左右两数组分别拷贝
    int len1 = q-p+1;
    int len2 = r-q;
    int* pArrLeft = new int(len1+1);
    for (int i=0;i<len1;++i)
    {
        pArrLeft[i] = a[p+i];
    }
    pArrLeft[len1] = MAX; //这里很巧妙,用作简化代码

    int* pArrRight = new int(len2+1);
    for (int i=0;i<len2;++i)
    {
        pArrRight[i] = a[q+1+i];
    }
    pArrRight[len2] = MAX;//这里很巧妙,用作简化代码

    //更新待排序数组a
    int i=0;
    int j=0;
    for (int k=p;k<=r;++k)
    {
        if (pArrLeft[i] <= pArrRight[j])
        {
            a[k] = pArrLeft[i];
            ++i;
        }
        else
        {
            a[k] = pArrRight[j];
            ++j;
        }
    }

    delete pArrLeft;
    delete pArrRight;

}

void merge_sort(int a[], int left, int right)
{
    if (left >= right) return;

    //当待排序序列长度为1时，递归开始"回升"
    int mid = (left+right)>>1;
    merge_sort(a, left, mid);
    merge_sort(a, mid+1, right);

    //从分治到左右两数组分别只有一个元素时，开始回溯
    merge(a, left, mid, right);

}
void print_array(int a[], int len)
{
    for (int i=0;i<len;++i)
    {
        std::cout << a[i] << ",";
    }
    std::cout << std::endl;
}
int main() {
    int a[] = {2,4,5,7,1,2,3,6};

    print_array(a,8);
    merge_sort(a, 0, 7);
    print_array(a,8);

    return 0;
}