摘要：歸并排序就這么簡單從前面已經講解了冒泡排序選擇排序插入排序快速排序了，本章主要講解的是歸并排序，希望大家看完能夠理解并手寫出歸并排序快速排序的代碼，然后就通過面試了如果我寫得有錯誤的地方也請大家在評論下指出。

從前面已經講解了冒泡排序、選擇排序、插入排序,快速排序了，本章主要講解的是歸并排序，希望大家看完能夠理解并手寫出歸并排序快速排序的代碼，然后就通過面試了！如果我寫得有錯誤的地方也請大家在評論下指出。

來源百度百科：

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

過程描述：

歸并過程為：比較a[i]和b[j]的大小，若a[i]≤b[j]，則將第一個有序表中的元素a[i]復制到r[k]中，并令i和k分別加上1；否則將第二個有序表中的元素b[j]復制到r[k]中，并令j和k分別加上1，如此循環下去，直到其中一個有序表取完，然后再將另一個有序表中剩余的元素復制到r中從下標k到下標t的單元。歸并排序的算法我們通常用遞歸實現，先把待排序區間[s,t]以中點二分，接著把左邊子區間排序，再把右邊子區間排序，最后把左區間和右區間用一次歸并操作合并成有序的區間[s,t]。

原理：

歸并操作的工作原理如下：
第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
第二步：設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
重復步驟3直到某一指針超出序列尾
將另一序列剩下的所有元素直接復制到合并序列尾

下面我就來做個小小的總結：

將兩個已排好序的數組合并成一個有序的數組,稱之為歸并排序

步驟：遍歷兩個數組，比較它們的值。誰比較小，誰先放入大數組中，直到數組遍歷完成

現在我有兩個已經排好順序的數組：int[] arr1 = {2, 7, 8}和int[] arr2 = {1, 4, 9}，我還有一個大數組來裝載它們int[] arr = new int[6];

那么，我將兩個數組的值進行比較，誰的值比較小，誰就放入大數組中！

首先，拿出arr1[0]和arr2[0]進行比較，顯然是arr2[0]比較小，因此將arr2[0]放入大數組中，同時arr2指針往后一格

所以，現在目前為止arr = {1}

隨后，拿arr1[0]和arr2[1]進行比較，顯然是arr1[0]比較小，將arr1[0]放入大數組中，同時arr1指針往后一格

所以，現在目前為止arr = {1,2}

隨后，拿arr1[1]和arr2[1]進行比較，顯然是arr2[1]比較小，將arr2[1]放入大數組中，同時arr2指針往后一格

所以，現在目前為止arr = {1,2,4}

........

遍歷到最后，我們會將兩個已排好序的數組變成一個已排好序的數組arr = {1,2,4,7,8,9}

從上面的演算我們就直到，歸并排序的前提是需要兩個已經排好順序的數組，那往往不會有兩個已經排好順序的數組給我們的呀(一般是雜亂無章的一個數組)，那這個算法是不是很雞肋的呢？？

其實并不是的，首先假設題目給出的數組是這樣子的：int[] arr = {2, 7, 8, 1, 4, 9};

當我們要做歸并的時候就以arr[3]也就元素為1的那個地方分開。是然后用一個指針L指向arr[0]，一個指針M指向arr[3]，用一個指針R指向arr[5](數組最后一位)。有了指針的幫助，我們就可以將這個數組切割成是兩個有序的數組了（操作的方式就可以和上面一樣了）

可是上面說了，一般給出的是雜亂無章的一個數組，現在還是達不到要求。比如給出的是這樣一個數組：int[] arrays = {9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8};

此時，我們就得用到分治的思想了：

那么我們也可以這樣想將int[] arr = {2, 7, 8, 1, 4, 9};數組分隔成一份一份的，arr[0]它是一個有序的"數組",arr[1]它也是一個有序的"數組",利用指針(L,M,R)又可以像操作兩個數組一樣進行排序。最終合成{2,7}.......再不斷拆分合并，最后又回到了我們的arr = {1,2,4,7,8,9}，因此歸并排序是可以排序雜亂無章的數組的

這就是我們的分治法--->將一個大問題分成很多個小問題進行解決，最后重新組合起來

實現步驟：

拆分

合并

........

    public static void main(String[] args) {
        int[] arrays = {9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8};
        mergeSort(arrays, 0, arrays.length - 1);

        System.out.println("公眾號：Java3y" + arrays);


    }

    /**
     * 歸并排序
     *
     * @param arrays
     * @param L      指向數組第一個元素
     * @param R      指向數組最后一個元素
     */
    public static void mergeSort(int[] arrays, int L, int R) {

        //如果只有一個元素，那就不用排序了
        if (L == R) {
            return;
        } else {

            //取中間的數，進行拆分
            int M = (L + R) / 2;

            //左邊的數不斷進行拆分
            mergeSort(arrays, L, M);

            //右邊的數不斷進行拆分
            mergeSort(arrays, M + 1, R);

            //合并
            merge(arrays, L, M + 1, R);

        }
    }


    /**
     * 合并數組
     *
     * @param arrays
     * @param L      指向數組第一個元素
     * @param M      指向數組分隔的元素
     * @param R      指向數組最后的元素
     */
    public static void merge(int[] arrays, int L, int M, int R) {

        //左邊的數組的大小
        int[] leftArray = new int[M - L];

        //右邊的數組大小
        int[] rightArray = new int[R - M + 1];

        //往這兩個數組填充數據
        for (int i = L; i < M; i++) {
            leftArray[i - L] = arrays[i];
        }
        for (int i = M; i <= R; i++) {
            rightArray[i - M] = arrays[i];
        }


        int i = 0, j = 0;
        // arrays數組的第一個元素
        int  k = L;


        //比較這兩個數組的值，哪個小，就往數組上放
        while (i < leftArray.length && j < rightArray.length) {

            //誰比較小，誰將元素放入大數組中,移動指針，繼續比較下一個
            // 等于的情況是保證“穩定”
            if (leftArray[i] <= rightArray[j]) {
                arrays[k] = leftArray[i];

                i++;
                k++;
            } else {
                arrays[k] = rightArray[j];
                j++;
                k++;
            }
        }

        //如果左邊的數組還沒比較完，右邊的數都已經完了，那么將左邊的數抄到大數組中(剩下的都是大數字)
        while (i < leftArray.length) {
            arrays[k] = leftArray[i];

            i++;
            k++;
        }
        //如果右邊的數組還沒比較完，左邊的數都已經完了，那么將右邊的數抄到大數組中(剩下的都是大數字)
        while (j < rightArray.length) {
            arrays[k] = rightArray[j];

            k++;
            j++;
        }
    }

我debug了一下第一次的時候，就可以更容易理解了：

將大數組的前兩個進行拆分，然后用數組裝載起來

比較小數組的元素哪個小，哪個小就先放入大數組中

上面的兩個步驟不斷循環，最后得出有序的數組：

來源：http://www.cnblogs.com/noKing/p/7940531.html

我這里整理一下要點，有興趣的同學可到上面的鏈接上閱讀：

當遞歸到規模足夠小時，利用插入排序

歸并前判斷一下是否還有必要歸并

只在排序前開辟一次空間

如果文章有錯的地方歡迎指正，大家互相交流。習慣在微信看技術文章，想要獲取更多的Java資源的同學，可以關注微信公眾號:Java3y