归并排序

原理

假设两个数组已经排好序，取他们各自的第一个数，小的放入c数组，然后相关计数器向前推进一格，当一个数组用完的时候，另一个数组剩余部分直接拷贝到C中

一般过程为

• 将n个元素分成各含n/2个元素的子序列

• 用归并排序法对这两个子序列递归地排序

• 合并这两个已经排序好的子序列得到排序结果

代码

/ 归并排序中的合并算法
void Merge(int array[], int left, int m, int right,int[] aux[])
{
    // aux临时数组 （若不使用临时数组，将两个有序数组合并为一个有序数组比较麻烦）
    int i; //第一个数组索引
    int j; //第二个数组索引
    int k; //临时数组索引
    
    for (i = left, j = m+1, k = 0; k <= right-left; k++) // 分别将 i, j, k 指向各自数组的首部。
    {
        //若 i 到达第一个数组的尾部，将第二个数组余下元素复制到 临时数组中
        if (i == m+1)
        {
            aux[k] = array[j++];
            continue;
        }
        //若 j 到达第二个数组的尾部，将第一个数组余下元素复制到 临时数组中
        if (j == right+1)
        {
            aux[k] = array[i++];
            continue;
        }
        //如果第一个数组的当前元素 比 第二个数组的当前元素小，将 第一个数组的当前元素复制到 临时数组中
        if (array[i] < array[j])
        {
            aux[k] = array[i++];
        }
        //如果第二个数组的当前元素 比 第一个数组的当前元素小，将 第二个数组的当前元素复制到 临时数组中
        else
        {
            aux[k] = array[j++];
        }
    }
    
    //将有序的临时数组 元素 刷回 被排序的数组 array 中，
    //i = left , 被排序的数组array 的起始位置
    //j = 0， 临时数组的起始位置
    for (i = left, j = 0; i <= right; i++, j++)
    {
        array[i] = aux[j];
    }
}
 
// 归并排序
void MergeSort(int array[], int start, int end, int TempArray[])
{
    if (start < end)
    {
        int i;
        i = (end + start) / 2;
        // 对前半部分进行排序
        MergeSort(array, start, i,TempArray);
        // 对后半部分进行排序
        MergeSort(array, i + 1, end,TempArray);
        // 合并前后两部分
        Merge(array, start, i, end,TempArray);
    }

注意复用了一个tempArray 因为在每次Merge时都新建一个临时数组会造成大量资源的浪费

算法分析

假设数组长度为n(2^N）
如果采取决策树 比较次数为logn!
采取归并排序

• 对于两个长度为1的数组 比较次数为1 合并次数为n/2
• 对于两个长度为2的数组 比较次数最好情况为2 最差情况为3 合并次数为n/4
• 对于两个长度为4的数组 比较次数最好情况为4 最差为7 合并次数为8/n
  如此推算 长度为n的数组
• 最好情况为 n*logn/2
• 最好情况为 n*logn-n+1

时间复杂度为O(NlogN)