1、基本思想

分析歸并排序之前胯陋，我們先來(lái)了解一下分治算法蕊温。

分治算法的基本思想是將一個(gè)規(guī)模為N的問(wèn)題分解為K個(gè)規(guī)模較小的子問(wèn)題袱箱，這些子問(wèn)題相互獨(dú)立且與原問(wèn)題性質(zhì)相同。求出子問(wèn)題的解寿弱，就可得到原問(wèn)題的解犯眠。

分治算法的一般步驟：

• 分解，將要解決的問(wèn)題劃分成若干規(guī)模較小的同類(lèi)問(wèn)題症革；
• 求解筐咧，當(dāng)子問(wèn)題劃分得足夠小時(shí)，用較簡(jiǎn)單的方法解決噪矛；
• 合并量蕊，按原問(wèn)題的要求，將子問(wèn)題的解逐層合并構(gòu)成原問(wèn)題的解艇挨。

歸并排序是分治算法的典型應(yīng)用残炮。

歸并排序先將一個(gè)無(wú)序的N長(zhǎng)數(shù)組切成N個(gè)有序子序列（只有一個(gè)數(shù)據(jù)的序列認(rèn)為是有序序列），然后兩兩合并缩滨，再將合并后的N/2（或者N/2 + 1）個(gè)子序列繼續(xù)進(jìn)行兩兩合并势就，以此類(lèi)推得到一個(gè)完整的有序數(shù)組。過(guò)程如下圖所示：

1.png

2脉漏、實(shí)例

歸并排序的核心思想是將兩個(gè)有序的數(shù)組歸并到另一個(gè)數(shù)組中苞冯，所以需要開(kāi)辟額外的空間。

第一步要理清歸并的思路侧巨。假設(shè)現(xiàn)在有兩個(gè)有序數(shù)組A和B舅锄，要將兩者有序地歸并到數(shù)組C中。我們用一個(gè)實(shí)例來(lái)推演：

2.png

上圖中司忱，A數(shù)組中有四個(gè)元素皇忿，B數(shù)組中有六個(gè)元素，首先比較A坦仍、B中的第一個(gè)元素鳍烁，將較小的那個(gè)放到C數(shù)組的第一位，因?yàn)樵撛鼐褪茿繁扎、B所有元素中最小的幔荒。上例中，7小于23锻离，所以將7放到了C中铺峭。

然后墓怀，用23與B中的其他元素比較汽纠，如果小于23，繼續(xù)按順序放到C中傀履；如果大于23虱朵，則將23放入C中莉炉。

23放入C中之后，用23之后的47作為基準(zhǔn)元素碴犬，與B中的其他元素繼續(xù)比較絮宁，重復(fù)上面的步驟。

如果有一個(gè)數(shù)組的元素已經(jīng)全部復(fù)制到C中了服协，那么將另一個(gè)數(shù)組中的剩余元素依次插入C中即可绍昂。至此結(jié)束。

按照上面的思路偿荷，用java實(shí)現(xiàn)：

    /**
     * 
     * - 歸并arrayA與arrayB到arrayC中
     * 
     * - @param arrayA 待歸并的數(shù)組A
     * 
     * - @param sizeA 數(shù)組A的長(zhǎng)度
     * 
     * - @param arrayB 待歸并的數(shù)組B
     * 
     * - @param sizeB 數(shù)組B的長(zhǎng)度
     * 
     * - @param arrayC 輔助歸并排序的數(shù)組
     */
    public static void merge(int[] arrayA, int sizeA, int[] arrayB, int sizeB, int[] arrayC) {

        int i = 0, j = 0, k = 0; // 分別當(dāng)作arrayA窘游、arrayB、arrayC的下標(biāo)指針

        while (i < sizeA && j < sizeB) { // 兩個(gè)數(shù)組都不為空
            if (arrayA[i] < arrayB[j]) { // 將兩者較小的那個(gè)放到arrayC中
                arrayC[k++] = arrayA[i++];
            } else {
                arrayC[k++] = arrayB[j++];
            }
        } // 該循環(huán)結(jié)束后跳纳，一個(gè)數(shù)組已經(jīng)完全復(fù)制到arrayC中了忍饰，另一個(gè)數(shù)組中還有元素

        // 后面的兩個(gè)while循環(huán)用于處理另一個(gè)不為空的數(shù)組
        while (i < sizeA) {
            arrayC[k++] = arrayA[i++];
        }

        while (j < sizeB) {
            arrayC[k++] = arrayA[j++];
        }

        for (int l = 0; l < arrayC.length; l++) { // 打印新數(shù)組中的元素
            System.out.print(arrayC[l] + "\t");
        }
    }

再歸并之前，還有一步工作需要提前做好寺庄，就是數(shù)組的分解艾蓝，可以通過(guò)遞歸的方法來(lái)實(shí)現(xiàn)。遞歸（Recursive）是算法設(shè)計(jì)中常用的思想斗塘。

這樣通過(guò)先遞歸的分解數(shù)組赢织，再合并數(shù)組就完成了歸并排序。完整的java代碼如下：

public class Sort {

    private int[] array; // 待排序的數(shù)組

    public Sort(int[] array) {
        this.array = array;
    }

    // 按順序打印數(shù)組中的元素
    public void display() {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println();
    }

    // 歸并排序

    public void mergeSort() {

        int[] workSpace = new int[array.length]; // 用于輔助排序的數(shù)組
        recursiveMergeSort(workSpace, 0, workSpace.length - 1);
    }

    /**
     * 
     * - 遞歸的歸并排序
     * 
     * - @param workSpace 輔助排序的數(shù)組
     * 
     * - @param lowerBound 欲歸并數(shù)組段的最小下標(biāo)
     * 
     * - @param upperBound 欲歸并數(shù)組段的最大下標(biāo)
     */
    private void recursiveMergeSort(int[] workSpace, int lowerBound, int upperBound) {

        if (lowerBound == upperBound) { // 該段只有一個(gè)元素逛拱，不用排序
            return;
        } else {
            int mid = (lowerBound + upperBound) / 2;
            recursiveMergeSort(workSpace, lowerBound, mid); // 對(duì)低位段歸并排序
            recursiveMergeSort(workSpace, mid + 1, upperBound); // 對(duì)高位段歸并排序
            merge(workSpace, lowerBound, mid, upperBound);
            display();
        }
    }

    /**
     * 
     * - 對(duì)數(shù)組array中的兩段進(jìn)行合并敌厘，lowerBound~mid為低位段，mid+1~upperBound為高位段
     * 
     * - @param workSpace 輔助歸并的數(shù)組朽合，容納歸并后的元素
     * 
     * - @param lowerBound 合并段的起始下標(biāo)
     * 
     * - @param mid 合并段的中點(diǎn)下標(biāo)
     * 
     * - @param upperBound 合并段的結(jié)束下標(biāo)
     */
    private void merge(int[] workSpace, int lowerBound, int mid, int upperBound) {

        int lowBegin = lowerBound; // 低位段的起始下標(biāo)
        int lowEnd = mid; // 低位段的結(jié)束下標(biāo)
        int highBegin = mid + 1; // 高位段的起始下標(biāo)
        int highEnd = upperBound; // 高位段的結(jié)束下標(biāo)
        int j = 0; // workSpace的下標(biāo)指針
        int n = upperBound - lowerBound + 1; // 歸并的元素總數(shù)

        while (lowBegin <= lowEnd && highBegin <= highEnd) {
            if (array[lowBegin] < array[highBegin]) { // 將兩者較小的那個(gè)放到workSpace中
                workSpace[j++] = array[lowBegin++];
            } else {
                workSpace[j++] = array[highBegin++];
            }
        }

        while (lowBegin <= lowEnd) {
            workSpace[j++] = array[lowBegin++];
        }

        while (highBegin <= highEnd) {
            workSpace[j++] = array[highBegin++];
        }

        for (j = 0; j < n; j++) { // 將歸并好的元素復(fù)制到array中
            array[lowerBound++] = workSpace[j];
        }

    }
}

用以下代碼測(cè)試：

int [] a = {6,2,7,4,8,1,5,3};
Sort sort = new Sort(a);
sort.mergeSort();

打印結(jié)果如下：

3.png

歸并的順序是這樣的：先將初始數(shù)組分為兩部分俱两，先歸并低位段，再歸并高位段曹步。對(duì)低位段與高位段繼續(xù)分解宪彩，低位段分解為更細(xì)分的一對(duì)低位段與高位段，高位段同樣分解為更細(xì)分的一對(duì)低位段與高位段讲婚，依次類(lèi)推尿孔。

上例中，第一步筹麸，歸并的是6與2活合，第二步歸并的是7和4，第三部歸并的是前兩步歸并好的子段[2,6]與[4,7]物赶。至此白指，數(shù)組的左半部分（低位段）歸并完畢，然后歸并右半部分（高位段）酵紫。

所以第四步歸并的是8與1告嘲，第四部歸并的是5與3错维，第五步歸并的是前兩步歸并好的字段[1,8]與[3,5]。至此橄唬，數(shù)組的右半部分歸并完畢赋焕。

最后一步就是歸并數(shù)組的左半部分[2,4,6,7]與右半部分[1,3,5,8]。

歸并排序結(jié)束仰楚。

3隆判、遞歸

在本文開(kāi)始對(duì)歸并排序的描述中，第一躺歸并是對(duì)所有相鄰的兩個(gè)元素歸并結(jié)束之后僧界，才進(jìn)行下一輪歸并蜜氨，并不是先歸并左半部分，再歸并右半部分捎泻，但是程序的執(zhí)行順序與我們對(duì)歸并排序的分析邏輯不一致飒炎，所以理解起來(lái)有些困難。

下面結(jié)合代碼與圖例來(lái)詳細(xì)分析一下歸并排序的過(guò)程笆豁。

虛擬機(jī)棧（VM Stack）是描述Java方法執(zhí)行的內(nèi)存模型郎汪，每一次方法的調(diào)用都伴隨著一次壓棧、出棧操作闯狱。

我們要排序的數(shù)組為：

int [] a = {6,2,7,4,8,1,5,3}

當(dāng)main()方法調(diào)用mergeSort()方法時(shí)煞赢，被調(diào)用的方法被壓入棧中，然后程序進(jìn)入mergeSort()方法：

    public void mergeSort() {
        int[] workSpace = new int[array.length]; // 用于輔助排序的數(shù)組
        recursiveMergeSort(workSpace, 0, workSpace.length - 1);
    }

此時(shí)哄孤，mergeSort()又調(diào)用了recursiveMergeSort(workSpace,0,7)方法照筑，recursiveMergeSort(workSpace,0,7)方法也被壓入棧中，在mergeSort()之上瘦陈。

然后凝危，程序進(jìn)入到recursiveMergeSort(workSpace,0,7)方法：

if (lowerBound == upperBound) { // 該段只有一個(gè)元素，不用排序
    return;
} else {
    int mid = (lowerBound + upperBound) / 2;
    recursiveMergeSort(workSpace, lowerBound, mid); // 對(duì)低位段歸并排序
    recursiveMergeSort(workSpace, mid + 1, upperBound); // 對(duì)高位段歸并排序
    merge(workSpace, lowerBound, mid, upperBound);
    display();
}

lowerBound參數(shù)值為0晨逝，upperBound參數(shù)值為7蛾默，不滿(mǎn)足lowerBound == upperBound的條件，所以方法進(jìn)入else分支捉貌，然后調(diào)用方法recursiveMergeSort(workSpace,0,3)支鸡，recursiveMergeSort(workSpace,0,3)被壓入棧中,此時(shí)棧的狀態(tài)如下：

4.png

然而，recursiveMergeSort(workSpace,0,3)不能立即返回趁窃，它在內(nèi)部又會(huì)調(diào)用recursiveMergeSort(workSpace,0,1)牧挣，recursiveMergeSort(workSpace,0,1)又調(diào)用了recursiveMergeSort(workSpace,0,0)，此時(shí)醒陆，棧中的狀態(tài)如下：

5.png

程序運(yùn)行到這里瀑构，終于有一個(gè)方法可以返回了結(jié)果了——recursiveMergeSort(workSpace,0,0)，該方法的執(zhí)行的邏輯是對(duì)數(shù)組中的下標(biāo)從0到0的元素進(jìn)行歸并统求，該段只有一個(gè)元素检碗，所以不用歸并，立即return码邻。

方法一旦return折剃，就意味著方法結(jié)束，recursiveMergeSort(workSpace,0,0)從棧中彈出像屋。這時(shí)候怕犁，程序跳到了代碼片段（二）中的第二行：recursiveMergeSort(workSpace,1,1)，該方法入棧己莺，recursiveMergeSort(workSpace,0,0)類(lèi)似奏甫，不用歸并，直接返回凌受，方法出棧阵子。

這時(shí)候程度跳到了代碼片段（二）中的第三行：merge(workSpace,0,0,1)，即對(duì)數(shù)組中的前兩個(gè)元素進(jìn)行合并（自然胜蛉，merge(workSpace,0,0,1)也伴隨著一次入棧與出棧）挠进。

至此，代碼片段（二）執(zhí)行完畢誊册，recursiveMergeSort(workSpace,0,1)方法出棧领突，程序跳到代碼片段（三）的第二行：recursiveMergeSort(workSpace,2,3)，該方法是對(duì)數(shù)組中的第三個(gè)案怯、第四個(gè)元素進(jìn)行歸并君旦，與執(zhí)行recursiveMergeSort(workSpace,0,1)的過(guò)程類(lèi)似，最終會(huì)將第三個(gè)嘲碱、第四個(gè)元素歸并排序金砍。

然后，程序跳到程序跳到代碼片段（三）的第三行：merge(workSpace,0,1,3)麦锯，將前面已經(jīng)排好序的兩個(gè)子序列（第一第二個(gè)元素為一組捞魁、第三第四個(gè)元素為一組）合并。

然后recursiveMergeSort(workSpace,0,3)出棧离咐，程序跳到代碼片段（四）的第二行：recursiveMergeSort(workSpace,4,7)谱俭，對(duì)數(shù)組的右半部分的四個(gè)元素進(jìn)行歸并排序，伴隨著一系列的入棧宵蛀、出棧昆著，最后將后四個(gè)元素排好。此時(shí)术陶，數(shù)組的左半部分與右半部分已經(jīng)有序凑懂。

然后程序跳到代碼片段（四）第三行：merge(workSpace,0,3,7)，對(duì)數(shù)組的左半部分與右半部分合并梧宫。

然后recursiveMergeSort(workSpace,4,7)出棧接谨，mergeSort()出棧摆碉，最后main()方法出棧，程序結(jié)束脓豪。

4巷帝、算法分析

先來(lái)分析一下復(fù)制的次數(shù)。

如果待排數(shù)組有8個(gè)元素扫夜，歸并排序需要分3層楞泼，第一層有四個(gè)包含兩個(gè)數(shù)據(jù)項(xiàng)的自數(shù)組，第二層包含兩個(gè)包含四個(gè)數(shù)據(jù)項(xiàng)的子數(shù)組笤闯，第三層包含一個(gè)8個(gè)數(shù)據(jù)項(xiàng)的子數(shù)組堕阔。合并子數(shù)組的時(shí)候，每一層的所有元素都要經(jīng)歷一次復(fù)制（從原數(shù)組復(fù)制到workSpace數(shù)組）颗味，復(fù)制總次數(shù)為3* 8=24次超陆，即層數(shù)乘以元素總數(shù)。

設(shè)元素總數(shù)為N浦马，則層數(shù)為log2N侥猬，復(fù)制總次數(shù)為N log2N。

其實(shí)捐韩，除了從原數(shù)組復(fù)制到workSpace數(shù)組退唠，還需要從workSpace數(shù)組復(fù)制到原數(shù)組，所以荤胁，最終的復(fù)制復(fù)制次數(shù)為2Nlog2N瞧预。

在大O表示法中，常數(shù)可以忽略仅政，所以歸并排序的時(shí)間復(fù)雜度為O(N log2N)垢油。

一般來(lái)講，復(fù)制操作的時(shí)間消耗要遠(yuǎn)大于比較操作的時(shí)間消耗圆丹，時(shí)間復(fù)雜度是由復(fù)制次數(shù)主導(dǎo)的滩愁。

下面我們?cè)賮?lái)分析一下比較次數(shù)。

在歸并排序中辫封，比較次數(shù)總是比復(fù)制次數(shù)少一些∠跬鳎現(xiàn)在給定兩個(gè)各有四個(gè)元素的子數(shù)組，首先來(lái)看一下最壞情況和最好情況下的比較次數(shù)為多少倦微。

6.png

第一種情況妻味，數(shù)據(jù)項(xiàng)大小交錯(cuò)，所以必須進(jìn)行7次比較欣福，第二種情況中责球，一個(gè)數(shù)組比另一個(gè)數(shù)組中的所有元素都要小，因此只需要4次比較。

當(dāng)歸并兩個(gè)子數(shù)組時(shí)雏逾，如果元素總數(shù)為N嘉裤，則最好情況下的比較次數(shù)為N/2，最壞情況下的比較次數(shù)為N-1栖博。

假設(shè)待排數(shù)組的元素總數(shù)為N屑宠，則第一層需要N/2次歸并，每次歸并的元素總數(shù)為2笛匙；則第一層需要N/4次歸并，每次歸并的元素總數(shù)為4犀变；則第一層需要N/8次歸并妹孙，每次歸并的元素總數(shù)為8……最后一次歸并次數(shù)為1，歸并的元素總數(shù)為N获枝〈勒總層數(shù)為log2N。

最好情況下的比較總數(shù)為：

N/2*(2/2)+ N/4*(4/2)+ N/8*(8/2)+...+1*(N/2) = (N/2)*log2N

最好情況下的比較總數(shù)為：

N/2*(2-1)+ N/4*(4-1)+ N/8*(8-1)+...+1*(N-1) = (N-N/2)+ (N-N/4)+(N-N/8)+...+(N-1) = N*log2N-(1+ N/2+N/4+..)< N*log2N

可見(jiàn)省店，比較次數(shù)介于(N/2)log2N與Nlog2N之間嚣崭。如果用大O表示法，時(shí)間復(fù)雜度也為O(Nlog2N)懦傍。