經典排序演算法 — C#版本(中)
歸併排序比較適合大規模得資料排序,借鑑了分治思想。
歸併排序原理
自古以來,分久必合合久必分。
我們可以這樣理解歸併排序,分-分到不能分為止,然後合併。
使用遞迴將問題一點一點分解,最後進行合併。
分而治之 (merge_sort)
提到遞推,我們使用地遞推解決問題,首先要分析出遞推公式、明確結束條件。
遞推公式: merge_sort(i...n)=merge( merge_sort(i...j), merge_sort(j+1...n) ) 結束條件: i>=n
分久必合(merge)
將兩個有序的陣列進行合併,這樣整個陣列也就是排序好的陣列了。
那麼怎麼進行合併呢?-- (i...j) 和 (j+1...n) 重新排序後,重新放入原來的陣列 (i...n)
兩組陣列 [3, 8, 9, 11] vs [1, 2, 5, 7]
兩個遊標 藍色 和 紅色
3>1,1小,1入新陣列,紅色遊標後移一位,繼續比較...
3>2,2小,2入陣列,紅色遊標後移一位
3<5,3小,3入陣列,藍色遊標後移一位
8>5,5小,5入陣列,紅色遊標後移一位
8>7,7小,7入陣列,紅色遊標後移,右側陣列全部轉移完畢
當有一組陣列全部轉移完畢,那麼剩下的一組中的全部元素依次轉入到新陣列中,新陣列正式成為一個有順序的陣列
通過以上兩點:遞推公式和合並思想,我們使用程式碼實現一下:
1、如下圖:遞迴方式 進行分解,然後使用合併程式碼進行合併。
1/// <summary> 2/// 遞迴呼叫 3/// </summary> 4/// <param name="a">原始陣列</param> 5/// <param name="p">分割點</param> 6/// <param name="r">結束位置</param> 7public static void MergrSortInternally(int[] a, int p, int r) 8{ 9//結束條件 10if (p >= r) 11return; 12 13//切割點 14int q = p + (r - p) / 2; 15 16//分而治之 17MergrSortInternally(a, p, q); 18 19MergrSortInternally(a, q + 1, r); 20 21//合併A(a, p, q) 和A(a, q + 1, r) 22Merage(a, p, q, r); 23 24} View Code
2、我們再來看看合併邏輯
引數:原始陣列,開始的地方,切割的地方,結束的地方
邏輯:兩個切割陣列的各自的遊標
申請同樣大小的臨時陣列
迴圈比較;小的入臨時,遊標後移;知道有一個數組空了為止
找到剩下不為空的那個陣列,將剩餘元素入臨時
將臨時陣列,找到原始陣列的對應為止進行覆蓋
1 /// <summary> 2/// 合併 3/// </summary> 4/// <param name="a">原始陣列</param> 5/// <param name="p">起始點</param> 6/// <param name="q">切割點</param> 7/// <param name="r">結束點</param> 8public static void Merage(int[] a, int p, int q, int r) 9{ 10// i 和 j = 兩個陣列的遊標 11int i = p; 12int j = q + 1; 13 14// 臨時陣列的遊標 15int k = 0; 16 17// 臨時陣列 18int[] temp = new int[r - p + 1]; 19 20//最小入隊,直到其中一個空空如也為止 21while (i <= q && j <= r) 22{ 23if (a[i] <= a[j]) 24{ 25temp[k] = a[i]; 26++k; 27++i; 28} 29else 30{ 31temp[k] = a[j]; 32++k; 33++j; 34} 35} 36 37// 找到另一個不為空的,找到剩下的元素 38int start = i; 39int end = q; 40 41if (j <= r) 42{ 43start = j; 44end = r; 45} 46 47// 剩餘陣列拷貝到臨時陣列 temp 48while (start <= end) 49{ 50temp[k++] = a[start++]; 51} 52 53// 將temp覆蓋到a[p...r] 54for (i = 0; i <= r - p; ++i) 55{ 56a[p + i] = temp[i]; 57} 58} View Code
歸併排序效能分析
Q:是不是穩定排序?
A:是
對於這兩組陣列 A[p...q] 和 A[q+1...r] 來說
程式碼中也是這樣實現的,a[i]就是左側陣列,a[j]就是右側陣列,保證相等時左側優先入隊即可。注意 等號位置。
Q:是否是原地排序?
A:當然不是
因為我們在合併程式碼時候,申請了同樣大小的記憶體空間。
但是對於這裡的歸併排序的空間複雜度又是多少呢?
雖然牽扯到了遞迴,但是臨時變數這裡會在一個函式結束後棧會釋放,所以 空間複雜度是O(n)
Q:時間複雜度又是多少呢?
A:O(n log n)
我們對 n 個元素的歸併排序時間記作 T(n),
分解函式分解兩個子陣列的時間是T(n/2)
合併函式時間複雜度是O(n)
T(1)=C; n=1
T(n)=2*T(n/2)+ n; n>1
T(n) = 2*T(n/2) + n
= 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
= 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
= 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
......
= 2^k * T(n/2^k) + k * n