歸併排序詳解遞歸和非遞歸實現

歸併排序的概念及定義

歸併排序（Merge）是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合并為整體有序序列。

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

歸併排序演算法穩定，數組需要O(n)的額外空間，鏈表需要O(log(n))的額外空間，時間複雜度為O(nlog(n))，演算法不是自適應的，不需要對數據的隨機讀取。

演算法思路：

把 n 個記錄看成 n 個長度為1的有序子表；

進行兩兩歸併使記錄關鍵字有序，得到 n/2 個長度為 2 的有序子表；

重複第步直到所有記錄歸併成一個長度為 n 的有序表為止。

此演算法的實現不像圖示那樣簡單，現分三步來討論。首先從宏觀上分析，首先讓子表表長 L=1 進行處理；不斷地使 L=2*L ，進行子表處理，直到 L>=n 為止，把這一過程寫成一個主體框架函數 mergesort 。

java代碼實現

public class MergeSortTest { public static void main(String[] args) { int[] data = new int[] { 4, 9, 11, 8, 67, 3, 4, 2, 32 }; print(data); mergeSort(data); System.out.println("排序後的數組："); print(data); } public static void mergeSort(int[] data) { sort(data, 0, data.length - 1); } public static void sort(int[] data, int left, int right) { if (left >= right) return; // 找出中間索引 int center = (left + right) / 2; // 對左邊數組進行遞歸 sort(data, left, center); // 對右邊數組進行遞歸 sort(data, center + 1, right); // 合并 merge(data, left, center, right); print(data); } /** * 將兩個數組進行歸併，歸併前面2個數組已有序，歸併後依然有序 * * @param data * 數組對象 * @param left * 左數組的第一個元素的索引 * @param center * 左數組的最後一個元素的索引，center+1是右數組第一個元素的索引 * @param right * 右數組最後一個元素的索引 */ public static void merge(int[] data, int left, int center, int right) { // 臨時數組 int[] tmpArray = new int[data.length]; // 右數組第一個元素索引 int midNew = center + 1; // third 記錄臨時數組的索引 int third = left; // 緩存左數組第一個元素的索引 int tmp = left; while (left

undefined

非遞歸實現 （引用上面的merge函數，重寫sort函數）

public class MergeSortTest { public static void main(String[] args) { int[] data = new int[] { 4, 9, 11, 8, 67, 3, 4, 2, 32 }; print(data); mergeSort(data); System.out.println("排序後的數組："); print(data); } public static void mergeSort(int[] data) { sort(data, 0, data.length - 1); } public static void sort(int[] data) { int n = data.length; //步長 int s = 2; int i; while(s

undefined

歸併排序總結：

（1）穩定性

歸併排序是一種穩定的排序。

（2）存儲結構要求

可用順序存儲結構。也易於在鏈表上實現。

（3）時間複雜度

對長度為n的文件，需進行 lgn趟二路歸併，每趟歸併的時間為O(n)，故其時間複雜度無論是在最好情況下還是在最壞情況下均是O(nlgn)。

（4）空間複雜度

需要一個輔助向量來暫存兩有序子文件歸併的結果，故其輔助空間複雜度為O(n)，顯然它不是就地排序。

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！