分冶法之合并排序

2017/2/26 使用模板改写，不支持char(char的结束符需要额外的改变)

合并排序的思想

对于一个需要排序的数组A[0_{n-1]，合并排序将它一分为二：A[0}[n/2]-1],A[[n/2]~n-1],并对每一个子数组递归排序，然后把这两个排好序的子数组合并为一个有序数组

伪代码

1. MergeSort,将数组递归拆分并使用Merge排序

      MergeSort(A[0~n-1])
    //递归调用mergesort对数组A[0~n-1]排序
    //输入：一个可排序数组A[0~n-1]
    //输出：非降序排列的数组A[0~n-1]
      if(n>1)
        copy A[0~[n/2]-1] to B[0~[n/2]-1]
        copy A[[n/2]~n-1] to C[0~[(n+1)/2]-1]//向上取整，请思考n为奇数的情况
        MergeSort(B[0~[n/2]-1])
        MergeSort(C[0~[(n+1)/2]-1])
        Merge(B,C,A)
    ```
2. Merge，真正实现排序的函数

Merge(B[0~p-1],C[0~q-1],A[0~p+q-1])
将两个有序数组合并为一个有序数组
//输入：两个有序数组B[0~p-1],C[0~q-1]
//输出：A[0~p+q-1]已经有序存放B和C中的元素
i=0,j=0,k=0;
while i<p and j<q do
    if B[i]<=C[j]
        A[k]=B[i];i++;
    else
        A[k]=C[j];j++;
    k++;

if i==p
    copy C[j~q-1] to A[k~p+q-1]
else
    copy B[i~q-1] to A[k~p+q-1]

#### 分析
1. MergeSort可以结合下图理解并思考n=2时的情况
![MergeSort](https://img.haomeiwen.com/i2400535/83ceb26984c6ebac.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

2. Merge很好理解，因为B，C都是有序数组，从B，C的下标i=0,j=0开始，找出两个中较小的一个，加入到A，并移动相应的i或j到下一位置，如果其中一个数组已经计算完毕，将另一个数组的剩余元素直接复制到A的尾部。


#### 代码
```c++
#include <iostream>
using namespace std;
void Merge(int *B, int p, int *C, int q, int *A);
void MergeSort(int *A, const int n);

int main()
{
    const int n = 8;
    int A[n] = {2,5,7,4,3,1,8,9};
    MergeSort(A, n);
    for (int i = 0; i < n; i++)
        cout << A[i] << "\t";

    system("pause");
    return 0;
}
void MergeSort(int *A, const int n)
{
    if (n>1)
    {
        int nB = n / 2;//向下取正
        int nC = (n + 1) / 2;//取上取整
        int *B = new int[nB];
        int *C = new int[nC];
        memcpy(B, A, nB * sizeof(int));
        memcpy(C, A + nB, nC * sizeof(int));
        MergeSort(B, nB);
        MergeSort(C, nC);
        Merge(B, nB, C, nC, A);
    }
}
void Merge(int *B, int p, int *C, int q, int *A)
{
    int i, j, k;
    i = j = k = 0;
    while (i < p&&j < q)
    {
    /*由A分配给B的元素肯定在分配给C的元素之前，
         当B[i]==C[j]应该选择B中的元素，确保稳定性。*/
        if (B[i] > C[j])
            A[k++] = C[j++];
        else
            A[k++] = B[i++];
    }
    if (i == p)//B已到尽头
        memcpy(A + k, C + j, (q - j) * sizeof(int));
    else
        memcpy(A + k, B + i, (p - i) * sizeof(int));

    free(B);
    free(C);
}

运行结果

结果