1. 基本思想

什么是歸并排序？？

歸并排序是基于歸并的排序。歸并，是將兩個或兩個以上的有序表合成一個有序表。

假設(shè)待排序的數(shù)組有 n 個元素，將數(shù)組看成是 n 個有序的子數(shù)組，每個子數(shù)組只有一個元素。然后兩兩合并，得到每個子數(shù)組長度為2。然后繼續(xù)兩兩合并，直到合并為長度為 n 的數(shù)組。

時間復(fù)雜度

平均復(fù)雜度是 O(nlogn)，最好復(fù)雜度是 O(nlogn)，最壞復(fù)雜度是 O(nlogn) 。

（圖片來源于網(wǎng)絡(luò)）

將原數(shù)組劃分子數(shù)組的過程看成是一棵二叉樹，那么數(shù)組劃分到每個子數(shù)組中只有一個元素時的二叉樹高度（遞歸深度）。最后一層是葉子節(jié)點，每個葉子節(jié)點是一個元素。那么，最后一層的節(jié)點個數(shù)是 n （數(shù)組長度）。假設(shè)二叉樹深度是 k ，那么，從 2^(k-1) = n 得到，k 是 logn 。合并的過程是從子數(shù)組（其中只有一個元素）開始向上合并

每次排序需要遍歷一次數(shù)組，時間是 O(n) 。一共需要 logn 趟排序（二叉樹的深度，遞歸深度）。所以時間復(fù)雜度是 O(nlogn) 。

空間復(fù)雜度

空間復(fù)雜度是 O(n) 。

每次排序中都需要一個數(shù)組暫時保存排序前的數(shù)組或者是排序后的結(jié)果數(shù)組，數(shù)組占用的空間是 n （數(shù)組的長度）。

使用場景

歸并排序是穩(wěn)定的排序。也就是，相等的元素的順序不會改變。歸并排序的速度僅次于快速排序。一般用于總體是無序的，但是子序列是相對有序的。

2. 代碼實現(xiàn)（java）

public void sort(int[] array) {mergeSort(array, 0, array.length); }public void mergeSort(int[] array, int low, int high) {if (low >= high) return;int mid = (low + high) / 2; // 將數(shù)組一分為二mergeSort(array, 0, mid); // 對左邊一半進(jìn)行排序mergeSort(array, mid, high); // 對右邊一半進(jìn)行排序merge(array, low, mid, high); // 將兩個有序子數(shù)組合并為一個有序數(shù)組 }// 將數(shù)組左右兩半合并為一個排好序的數(shù)組。左右兩個子數(shù)組已經(jīng)是排好序的數(shù)組 public void merge(int[] array, int low, int mid, int high) {// 將數(shù)組array復(fù)制到一個新數(shù)組copy中，將排序完成后的值寫入原數(shù)組arrayint[] copy = Arrays.copyOf(array, array.length); // 復(fù)制int i = low, j = mid, k = low;// 逐一比較兩個子數(shù)組，小者排在前面。直至其中一個數(shù)組全部寫入結(jié)果數(shù)組中while (i < mid && j < high) {if (copy[i] <= copy[j]) array[k++] = copy[i++]; // 相等的元素，相對位置不改變else array[k++] = copy[j++];}// 如果左邊的子數(shù)組中剩余的數(shù)據(jù)寫入數(shù)組中while (i < low) array[k++] = copy[i++];// 如果右邊的子數(shù)組中剩余的數(shù)據(jù)寫入數(shù)組中while (j < high) array[k++] = copy[j++]; }/**********************************************************************/ // 將兩個有序子數(shù)組合并為一個有序數(shù)組。第一個有序子數(shù)組是[low,mid)，第二個有序子數(shù)組是[mid,high) public void merge(int[] array, int low, int mid, int high) {// 將數(shù)組array復(fù)制到一個新數(shù)組copy中，將排序完成后的值寫入原數(shù)組arrayint[] res = new int[array.length]; // 復(fù)制int i = low, j = mid, k = low;// 逐一比較兩個子數(shù)組，小者排在前面。直至其中一個數(shù)組全部寫入結(jié)果數(shù)組中while (i < mid && j < high) {if (array[i] <= array[j]) res[k++] = array[i++];else res[k++] = array[j++];}// 如果左邊的子數(shù)組中剩余的數(shù)據(jù)寫入數(shù)組中while (i < low) res[k++] = array[i++];// 如果右邊的子數(shù)組中剩余的數(shù)據(jù)寫入數(shù)組中while (j < high) res[k++] = array[j++];// 把結(jié)果數(shù)組res中[low,high)中的部分復(fù)制到原數(shù)組中，從而改變原數(shù)組for (i = low, k = low; i < high; i++, k++) {array[k] = res[i];} }

3. 代碼說明

public void mergeSort(int[] array, int low, int high) {if (low >= high) return;int mid = (low + high) / 2; // 將數(shù)組一分為二mergeSort(array, 0, mid); // 對左邊一半進(jìn)行排序mergeSort(array, mid, high); // 對右邊一半進(jìn)行排序merge(array, low, mid, high); // 將排好序的兩部分合并為一個排好序的數(shù)組 }

mergeSort() 是一個遞歸函數(shù)。遞歸的過程就像是一個下樓梯的過程。在遞歸時，調(diào)用一次自己，就下一個臺階（調(diào)用），直到下到最后一個（終止條件），然后想上返回到第一個臺階（回溯）。

歸并排序，向下劃分，向上合并的過程。在向下調(diào)用自身的過程，把數(shù)組一分為二，一次次的劃分，直到數(shù)組中的一個元素單獨成為一個子數(shù)組。mergeSort(array, low, mid) 和mergeSort(array, mid, high) 是調(diào)用自身劃分的過程。合并是發(fā)生在劃分之后，merge(array, low, mid, high) 是把兩個升序的子數(shù)組合并為一個升序的數(shù)組，也是遞歸中回溯做的事情。

總結(jié)

以上是生活随笔為你收集整理的归并排序 MergeSort的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。