歸並排序

思想

歸並排序（merge sort）是建立在歸並操作上的一種有效的排序算法,它以 O(nlogn) 最壞情形運行時間運行。它是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列：即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並。歸並排序可並行實現。

歸並排序示例圖如下：

實現

合並操作

基本的合並算法是取兩個輸入數組 A 和 B、一個輸出數組 C，以及三個計數器 Aptr， Bptr， Cptr。它們初始置於對應數組的開始端。A[Aptr]和 B[Bptr]中的較小者被拷貝到 C 中的下一個位置，相關的計數器向前推進一步。當兩個輸入表有一個用完時，則將另一個表中剩余部分拷貝到 C 中。

如果對 Merge 的每個遞歸調用均局部聲明一個臨時數組，那麼在任一時刻就可能有 log N 個臨時數組處在活動期，這對於小內存機器是致命的。另一方面，如果 Merge 例程動態分配並釋放最小量臨時內存，那麼由 malloc 占用的時間會很多。因此，可將輸入數組分成兩個輸入數組。

/***    @description 對數組a的 a[leftPos, rightPos - 1] 和 a[rightPos, rightEnd] 兩部分進行合並操作，結果暫存到tmpArray中，最後拷貝回數組a。
*/
void Merge(ElementType a[], ElementType tmpArray[], int leftPos, int rightPos, int rightEnd)
{
    int i, leftEnd, numOfElements, tmpPos;
 
    leftEnd = rightPos - 1;
    tmpPos = leftPos;
    numOfElements = rightEnd - leftPos + 1;       
 
    //main loop
    while (leftPos <= leftEnd && rightPos <= rightEnd)
        if (a[leftPos] < a[rightPos])
            tmpArray[tmpPos++] = a[leftPos++];
        else
            tmpArray[tmpPos++] = a[rightPos++];
 
    //get rest of first half
    while (leftPos <= leftEnd)
        tmpArray[tmpPos++] = a[leftPos++];
 
    //get rest of second half
    while (rightPos <= rightEnd)
        tmpArray[tmpPos++] = a[rightPos++];
 
    //copy tmpArray back
    for (i = 0; i < numOfElements; ++i, rightEnd--)
        a[rightEnd] = tmpArray[rightEnd];
}

歸並排序

/***    @description 歸並排序主算法，對數組a[left, right] 進行歸並排序，使用到了暫存數組tmpArray。
*/
void MSort(ElementType a[], ElementType tmpArray[], int left, int right)
{
    int center;
 
    if (left < right)
    {
        center = (left + right) / 2;
        MSort(a, tmpArray, left, center);
        MSort(a, tmpArray, center + 1, right);
        Merge(a, tmpArray, left, center + 1, right);
    }
}

算法主體

/***    @description 歸並排序算法，封裝了開辟臨時存儲空間的操作。
*/
void MergeSort(ElementType a[], int n)
{
    ElementType *tmpArray;
 
    tmpArray = (ElementType *)malloc(sizeof(ElementType) * n);
    if (tmpArray != NULL)
    {
        MSort(a, tmpArray, 0, n - 1);
        free(tmpArray);
    }
    else
        puts("No space of tmp Array!");
}