排序演算法之——歸併排序(兩種方法及其優化)
本文將圍繞程式碼從多個方面分析歸併演算法,歸併的操作很簡單,稍加思考便能深刻理解。
1、演算法思想:
要將一個數組排序,可以(遞迴地)將陣列分成兩半分別排序,然後將兩邊歸併起來。歸併演算法最吸引人的地方是它能保證將任意長度為N的陣列排序的時間與NlgN成正比。
主要缺點是需要與N成正比的額外空間。
(示意圖1)
2、原地歸併的抽象方法
實現歸併最直截了當的方法是將兩個陣列歸併到第三個陣列,實現的方法很簡單,從左到右逐一比較兩陣列的第一位元素,將小的一個放入第三個陣列(假設兩陣列已經有序),完成操作後第三個陣列就是有序的。瞭解了思路,我們直接看程式碼。
1public static void merge(Comparable[] a, int lo, int mid, int hi) { 2int i = lo, j = mid + 1; 3for (int k = lo; k <= hi; k++) { 4aux[k] = a[k]; 5} 6for (int k = lo; k <= hi; k++) { 7if (i > mid) { 8a[k] = aux[j++]; 9} else if (j > hi) { 10a[k] = aux[i++]; 11} else if (less(aux[i], aux[j])) { 12a[k] = aux[i++]; 13} else { 14a[k] = aux[j++]; 15} 16} 17 18}
主要操作就是第二個for迴圈裡的四個判斷:
1、陣列1走完(將陣列2當前元素放入陣列3)
2、陣列2走完(將陣列1當前元素放入陣列3)
3、陣列1當前元素小於陣列2當前元素(將陣列1當前元素放入陣列3)
4、陣列2當前元素小於等於陣列1當前元素(將陣列2當前元素放入陣列3)
(示意圖2)
3、自頂向下的歸併排序
如果能將兩個子陣列排序,就能通過並歸兩個子陣列來對整個陣列排序,這一切是通過遞迴實現的,也叫遞迴歸併。直接看程式碼:
1 public class Merge{ 2private static Comparable[] aux; 3public static void sort(Comparable[] a) { 4aux = a.clone();// 一次性分配空間 5sort(a,0, a.length - 1); 6} 7 8private static void sort(Comparable[] a,int lo, int hi) { 9if (hi <= lo) { 10return; 11} 12int mid = lo + (hi - lo) / 2; 13sort(aux,a, lo, mid);//左半邊排序 14sort(aux,a, mid + 1, hi);//右半邊排序 15merge(a,aux,lo, mid, hi);//歸併結果(參考原地歸併的抽象方法) 16} 17 }
示意圖:
(示意圖3)
上圖只是merge方法的軌跡,sort方法也極為重要,要想理解就必須知道sort方法呼叫的軌跡(這裡請讀者自己先寫出sort的軌跡再看下面的答案)
sort(a,0,7)
將左半部分排序
sort(a,0,3)
sort(a,0,1)
merge(a,0,0,1)
sort(a,2,3)
merge(a,2,2,3)
將右半部分排序
sort(a,4,7)
sort(a,4,5)
merge(a,4,4,5)
sort(a,6,7)
merge(a,6,6,7)
歸併結果
merge(a,0,3,7 )
4、自底向上的歸併排序
我們已經知道,自頂向下採用的是遞迴的方法,而自底向上則是循序漸進得解決問題,採用了迴圈的方法。通過下圖可以很容易看出兩種方式的區別:
下面上程式碼:
1public static void sort(Comparable[] a) { 2int n = a.length; 3aux = new Comparable[n]; 4for (int sz = 1; sz < n; sz = sz + sz) { 5for (int lo = 0; lo < n - sz; lo += sz + sz) { 6merge(a, lo, lo + sz - 1, Math.min(lo + 2 * sz - 1, n - 1));// 最後一次並歸的第二個子陣列可能比第一個小此時lo+2*sz-1越界 7} 8} 9}
讀者自行考慮自底向上方法的執行軌跡。
5、三項優化(程式碼在後面的程式碼演示中)
①對小規模子陣列使用插入排序
用不同的方法處理小規模陣列能改進大多遞迴演算法的效能,在小陣列上上,插入排序可能比並歸排序更快。
②測試陣列是否有序
根據歸併排序的特點,每次歸併的兩個小陣列都是有序的,當a[mid]<=a[mid+1]時我們可以跳過merge方法,這樣並不影響排序的遞迴呼叫。
③不將元素複製到輔助陣列
我們可以節省將陣列複製到輔助陣列的時間,這需要一些技巧。先克隆原陣列到輔助陣列,然後在之後的遞迴交換輸入陣列和輔助陣列的角色(通過看程式碼更容易理解)
(畫方框的為每次的輸出陣列)
6、程式碼演示(java):
1 public class Merge implements Comparable<Merge> {// 歸併排序(優化前) 2private static Comparable[] aux; 3 4private static boolean less(Comparable v, Comparable w) { 5return v.compareTo(w) < 0; 6} 7 8@Override 9public int compareTo(Merge arg0) { 10// TODO Auto-generated method stub 11return 0; 12} 13 14public static void merge(Comparable[] a, int lo, int mid, int hi) {// 原地歸併的抽象方法 15int i = lo, j = mid + 1; 16for (int k = lo; k <= hi; k++) { 17aux[k] = a[k]; 18} 19for (int k = lo; k <= hi; k++) { 20if (i > mid) { 21a[k] = aux[j++]; 22} else if (j > hi) { 23a[k] = aux[i++]; 24} else if (less(aux[j], aux[i])) { 25a[k] = aux[j++]; 26} else { 27a[k] = aux[i++]; 28} 29} 30} 31 32public static void sort(Comparable[] a) { 33aux = new Comparable[a.length]; 34sort(a, 0, a.length - 1); 35} 36 37private static void sort(Comparable[] a, int lo, int hi) { 38/* 39* 自頂向下的並歸排序 三個改進 40*/ 41if (hi <= lo) { 42return; 43} 44int mid = lo + (hi - lo) / 2; 45sort(a, lo, mid); 46sort(a, mid + 1, hi); 47merge(a, lo, mid, hi); 48} 49 50private static void exch(Comparable[] a, int j, int i) { 51// TODO Auto-generated method stub 52Comparable temp; 53temp = a[j]; 54a[j] = a[i]; 55a[i] = temp; 56} 57 58public static void main(String[] args) { 59Merge mg = new Merge(); 60Comparable a[] = { 8, 1, 6, 8, 4, 6, 9, 7, 1, 2, 3, 4, 8, 5, 2, 6, 4, 3, 8 }; 61mg.sort(a); 62for (int i = 0; i < a.length; i++) { 63System.out.print(a[i] + " "); 64} 65} 66 }
1 public class MergeX implements Comparable<Merge> {// 歸併排序(優化後) 2private static Comparable[] aux; 3 4private static boolean less(Comparable v, Comparable w) { 5return v.compareTo(w) < 0; 6} 7 8@Override 9public int compareTo(Merge arg0) { 10// TODO Auto-generated method stub 11return 0; 12} 13 14public static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {// 原地歸併的抽象方法 15int i = lo, j = mid + 1; 16// for (int k = lo; k <= hi; k++) { 17// aux[k] = a[k]; 18// } 19for (int k = lo; k <= hi; k++) { 20if (i > mid) { 21a[k] = aux[j++]; 22} else if (j > hi) { 23a[k] = aux[i++]; 24} else if (less(aux[j], aux[i])) { 25a[k] = aux[j++]; 26} else { 27a[k] = aux[i++]; 28} 29} 30} 31 32public static void sort(Comparable[] a) { 33aux = a.clone();// 一次性分配空間 34sort(a, aux, 0, a.length - 1); 35} 36 37private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) { 38/* 39* 自頂向下的並歸排序 三個改進 40*/ 41// if (hi <= lo) { 42// return; 43// } 44int mid = lo + (hi - lo) / 2; 45if (hi - lo <= 7) {// 對小規模子陣列使用插入排序 46//System.out.println("insert!"); 47insertionSort(a, lo, hi); 48return; 49} 50sort(aux, a, lo, mid); 51sort(aux, a, mid + 1, hi); 52if (!less(aux[mid + 1], aux[mid])) {// 已經有序時跳過merge(a中lo到mid mid到hi分別都是有序的) 53System.arraycopy(aux, lo, a, lo, hi-lo+1); 54return; 55} 56merge(a, aux, lo, mid, hi); 57} 58 59private static void insertionSort(Comparable[] a, int lo, int hi) { 60for (int i = lo; i <= hi; i++) 61for (int j = i; j > lo && less(a[j], a[j - 1]); j--) 62exch(a, j, j - 1); 63} 64 65private static void exch(Comparable[] a, int j, int i) { 66// TODO Auto-generated method stub 67Comparable temp; 68temp = a[j]; 69a[j] = a[i]; 70a[i] = temp; 71} 72 73public static void main(String[] args) { 74MergeX mgx = new MergeX(); 75Comparable a[] = { 8, 1, 6, 8, 4, 6, 9,7,1, 2, 3,4,8,5,2,6,4,3,8}; 76mgx.sort(a); 77for (int i = 0; i < a.length; i++) { 78System.out.print(a[i] + " "); 79} 80} 81 }