歸並排序的分析及實現

思想：將兩個（或以上）的有序表組成新的有序表。

說明：

（1）更實際的意義：可以把一個長度為n 的無序序列看成是 n 個長度為 1 的有序子序列 ，首先做兩兩歸並，得到 én / 2ù 個長度為 2 的子序列 ；再做兩兩歸並，…，如此重復，直到最後得到一個長度為 n 的有序序列。

（2）性能分析。空間性能：輔助空間 O(n)。時間復雜度：O(nlogn)。穩定性：穩定。

（3）雖然歸並排序的運行時間是O(nlogn)，但它很難用於主存排序，主要問題在於合並兩個排序的表需要線性附加內存，在整個算法中還要花費將數據拷貝到臨時數組再拷貝回來這樣一些附加的工作，其結果嚴重放慢了排序的速度。

（4）歸並排序與堆排序和快速排序相比，最大的特點是它是一種穩定的排序方法，所使用的比較次數幾乎是最優的。

（5）歸並排序的一種變形也可非遞歸實現，但對於內部排序而言，人們還是選擇快速排序。

#include <stdio.h>
#include <stdlib.h>

void Merge(int arr[], int tmpArr[], int left, int mid, int right)
{
    if (!arr || !tmpArr)
    {
        printf("Error Appear!\n");
        return;
    }

    int lEnd = mid;                                    //左子數組上界
    int rStart = mid + 1;                            //右子數組下界
    int cPos = left;   
    int arrNum = right - left + 1;

    while (left <= lEnd && rStart <= right)
    {
        if (arr[left] <= arr[rStart])
        {
            tmpArr[cPos++] = arr[left++];
        }
        else
        {
            tmpArr[cPos++] = arr[rStart++];
        }
    }

    while (left <= lEnd)
    {
        tmpArr[cPos++] = arr[left++];
    }
    while (rStart <= right)
    {
        tmpArr[cPos++] = arr[rStart++];
    }

    for (int i = 0; i < arrNum; i++, right--)
    {
        arr[right] = tmpArr[right];
    }
}

void MSort(int arr[], int tmpArr[], int left, int right)
{
    if (!arr || !tmpArr)
    {
        printf("Error Appear!\n");
        return;
    }

    int mid;
    if (left < right)
    {
        mid = (left + right) / 2;
        MSort(arr, tmpArr, left, mid);
        MSort(arr, tmpArr, mid + 1, right);
        Merge(arr, tmpArr, left, mid, right);
    }
}

void MergeSort(int arr[], int len)
{
    int *tmpArr = (int *)malloc(sizeof(int) * len);
    if (tmpArr != NULL)
    {
        MSort(arr, tmpArr, 0, len - 1);
        free(tmpArr);
    }
    else
    {
        printf("Malloc Failed!\n");
        return;
    }
}

int main(void)
{
    int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    MergeSort(arr, 10);

    for (int i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm