面試 11：玩轉 Java 歸并排序

面試 11：Java 玩轉歸并排序

前面講了冒泡、選擇、插入三種簡單排序，時間複雜度都是 O(n²)，今天，我們終于迎來了更進階的排序：歸并排序。

雖然在這之前還有希爾排序和堆排序，但由于時間關系，我們這裡就直接跳過，确實感興趣的請直接 Google。

歸并排序

我們總是可以将一個數組一分為二，然後二分為四，直到每一組隻有兩個元素，這可以了解為個遞歸的過程，然後将兩個元素進行排序，之後再将兩個元素為一組進行排序。直到所有的元素都排序完成。同樣我們來看下邊這個動圖。

圖檔來源于網絡

歸并排序算法是采用分治法的一個非常典型的應用，且各層分治遞歸可以同時進行。

歸并算法的思想

歸并算法其實可以分為遞歸法和疊代法（自底向上歸并），兩種實作對于最小集合的歸并操作思想是一樣的。差別在于如何劃分數組，我們先介紹下算法最基本的操作：

1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并後的序列；
2. 設定兩個指針，最初位置分别為兩個已經排序序列的起始位置；
3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；
4. 重複步驟 3 直到某一指針到達序列尾；
5. 将另一序列剩下的所有元素直接複制到合并序列尾。

我們來看看 Java 遞歸代碼是怎麼實作的：

public class Test09 {

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void printArr(int[] arr) {
        for (int anArr : arr) {
            System.out.print(anArr + " ");
        }
    }

    private static void mergeSort(int[] arr) {
        if (arr == null)
            return;
        mergeSort(arr, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int start, int end) {
        if (start >= end)
            return;
        // 找出中間索引
        int mid = start + (end - start >> 1);
        // 對左邊數組進行遞歸
        mergeSort(arr, start, mid);
        // 對右邊數組進行遞歸
        mergeSort(arr, mid + 1, end);
        // 合并
        merge(arr, start, mid, end);
    }

    private static void merge(int[] arr, int start, int mid, int end) {
        // 先建立一個臨時數組，用于存放排序後的資料
        int[] tmpArr = new int[arr.length];

        int start1 = start, end1 = mid, start2 = mid + 1, end2 = end;
        // 建立一個下标
        int pos = start1;
        // 緩存左邊數組的第一個元素的索引
        int tmp = start1;
        while (start1 <= end1 && start2 <= end2) {
            // 從兩個數組中取出最小的放入臨時數組
            if (arr[start1] <= arr[start2])
                tmpArr[pos++] = arr[start1++];
            else
                tmpArr[pos++] = arr[start2++];
        }
        // 剩餘部分依次放入臨時數組，實際上下面兩個 while 隻會執行其中一個
        while (start1 <= end1) {
            tmpArr[pos++] = arr[start1++];
        }
        while (start2 <= end2) {
            tmpArr[pos++] = arr[start2++];
        }
        // 将臨時數組中的内容拷貝回原來的數組中
        while (tmp <= end) {
            arr[tmp] = tmpArr[tmp++];
        }

    }

    public static void main(String[] args) {
        int[] arr = {6, 4, 2, 1, 8, 3, 7, 9, 5};
        mergeSort(arr);
        printArr(arr);
    }
}
           

歸并排序算法總的時間複雜度是 O(nlogn)，而且這是歸并排序算法中最好、最壞、平均的時間性能。

而由于在歸并排序過程中需要與原始記錄序列同樣數量的存儲空間存放歸并結果以及遞歸時壓入棧的資料占用的空間：n + logn，是以空間複雜度為 O(n)。

總結

歸并排序雖然比較穩定，在時間上也是非常有效的，但是這種算法很消耗空間，一般來說隻有在外部排序才會采用這個方法，但在内部排序不會用這種方法，而是用快速排序。明天，我們将帶來排序算法中的王牌：快速排序。