合并排序(归并排序)

1 合并排序采用的是分治策略

a 分解：将原问题分解成一系列子问题

b 解决：递归的解决各个子问题，若问题足够小，则直接求解

c 合并：将子问题的结果合并成原问题的解

2 将n个元素分成各含n/2个元素的子序列（重复执行分解动作，直到子程序元素足够小）

3 单个元素被视为已排好序的

4 为做合并需要引入辅助操作

5 合并算法的算法复杂度为 nlgn（低为2）

注意：实现时需要考虑起始下标为 0 或者为 1 的情况，

　　　两种方法均可实现（原理相同），但下标的不同直接导致分解方式的不同，

　　　遇到问题时可在关键位置加入 '打印关键值' 来调试程序

void Merge(int array[], int start, int middle, int end) //合并操作的辅助函数
{
    int n1= middle-start; //计算数组大小
    int n2= end-middle;

    int *left = new int[n1]; //动态分配内存
    int *right = new int[n2];

    for(int i=0; i<n1; ++i)  //为已排好序的两组元素 分别赋值到 新的数组
    {
        left[i] = array[start+i]; //从start开始
    }
    for (int j=0; j<n2; ++j)
    {
        right[j] = array[middle+j];  //从middle开始
    }

    int i=0, j=0;
    for(int key=start; key<end; ++key)  
    {
        if (i<n1 && left[i] <= right[j])     //从已排好序的两个数组中分别抽取数据，进行比较
        {
            array[key] = left[i++];            //插入到最初的数组里，更新下标
        }
        else if ( j<n2 && right[j] <= left[i])
        {
            array[key] = right[j++];
        }
        else if (i==n1 && j<n2)        //考虑left数组为空 但right数组依然还有数据时
        {
            array[key] = right[j++];
        }
        else if (j==n2 && i<n1)        //考虑right数组为空 但left数组依然还有数据时
        {
            array[key] = left[i++];
        }
    }

    delete [] left;        //释放内存
    delete [] right;
}
//第一次调用该函数，start的下标为从零开始，
//也可以不考虑下标从1开始，但实现方式（主要是分解条件及分解方法 注意下标）需要做相应修改
void MergeSort(int array[], int start, int end) 
{
    if(start+1 < end)   //分解条件 子问题只有两个元素 例如 start=0，end=1 结束分解
    {
        int middle = (start+end)/2; //分解方式 子问题为原问题的一半
        //for (int i=0; i<10; ++i)
        //{
        //    cout << array[i] << " ";
        //}
        //cout << endl;
        MergeSort(array,start,middle);  //分解方法 middle在此作为边界条件（其功能与end相同充当哨兵位，不能访问该下标） 
        MergeSort(array,middle,end);    //middle在此作为起始下标
        Merge(array,start,middle,end);  //例如 merge（8,9,10） 实际进行排序的只有 array[8] 与 array[9]
        //for (int i=0; i<10; ++i)
        //{
        //    cout << array[i] << " ";
        //}
        //cout << endl;
    }
}
void main()
{
    //判断是否有内存泄露，需要加头文件#include <crtdbg.h>
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF|_CRTDBG_LEAK_CHECK_DF); 

    int Array[10] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};

    MergeSort(Array, 0, 10);

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

    system("pause");
}