數據結構和算法14 之歸並排序

歸並算法的中心是歸並兩個已經有序的數組。歸並兩個有序數組A和B，就生成了第三個數組C，數組C包含數組A和B的所有數據項，並且使它們有序的排列在數組C中。首先我們來看看歸並的過程，然後看它是如何在排序中使用的。

假設有兩個有序數組，不要求有相同的大小。設數組A有4個數據項，數組B有6個數據項，它們要被歸並到數組C中，開始時數組C有10個存儲空間，歸並過程如下圖所示：

歸並排序的思想是把一個數組分成兩半，排序每一半。然後用merge方法將數組的兩半歸並成一個有序的數組。被分的每一半使用遞歸，再次劃分排序，直到得到的子數組只含有一個數據項為止。正如上面所說的，歸並排序需要額外的一個和AB兩個數組總和相等的空間，如果初始數組幾乎沾滿了整個存儲器，那麼歸並排序就不能工作了。

歸並排序的思想很簡單，下面我們來看看具體實現：

public void mergeSort(int[] source) {
    int[] workSpace = new int[source.length];
    recMergeSort(source,workSpace, 0, source.length-1);
}

private void recMergeSort(int[] source, int[] workSpace, int lowerBound, int upperBound) {
    if(lowerBound == upperBound) {
        return;
    }
    else {
        int mid = (lowerBound + upperBound) / 2;
        recMergeSort(source, workSpace, lowerBound, mid); //左邊排
        recMergeSort(source, workSpace, mid+1, upperBound); //右邊排
        merge(source, workSpace, lowerBound, mid+1, upperBound);//歸並
    }
}

private void merge(int[] a, int[] workSpace, int lowPtr, int highPtr, int upperBound) {
    int j = 0;
    int lowerBound = lowPtr;
    int mid = highPtr - 1;
    int n = upperBound - lowerBound + 1;
    while(lowPtr <= mid && highPtr <= upperBound) {
        if(a[lowPtr] < a[highPtr]) {
            workSpace[j++] = a[lowPtr++];
        }
        else {
            workSpace[j++] = a[highPtr++];
        }
    }
    while(lowPtr <= mid) {
        workSpace[j++] = a[lowPtr++];
    }
    
    while(highPtr <= upperBound) {
        workSpace[j++] = a[highPtr++];
    }
    
    for(j = 0; j < n; j++) {
        a[lowerBound + j] = workSpace[j];
    }
}

算法分析：歸並排序的運行時間最差、最好和平均都是O(NlogN)，但是它需要額外的存儲空間，這在某些內存緊張的機器上會受到限制。歸並算法是由分割和歸並兩部分組成的，對於分各部分，如果我們使用二分查找，時間是O(NlogN)，在最後歸並的時候時間是O(N)，所以總時間是O(NlogN)。空間復雜度為O(N)。

歸並排序就寫這麼多，如有錯誤之處，歡迎留言指正~

_____________________________________________________________________________________________________________________________________________________