前言：
寫這篇博客主要作為自己學習演算法時的筆記，加深理解，可能會有很多疏漏歡迎指正，
代碼的實作對邊界的處理都是左閉右閉的區間，如果定義不同相應的代碼也會有所區別，
參考文章：圖解排序演算法(四)之歸并排序
【圖解資料結構】 一組影片徹底理解歸并排序
1.歸并排序
1.1 演算法程序
- 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
- 設定兩個指標，最初位置分別為兩個已經排序序列的起始位置
- 比較兩個指標所指向的元素，選擇相對小的元素放入到合并空間，并移動指標到下一位置
- 重復步驟3直到某一指標超出序列尾
- 將另一序列剩下的所有元素直接復制到合并序列尾
借這位博主（感謝大佬精心制作的圖，太清晰易懂了）的圖片幫助理解：
1.2 可視化展示：
圖源：https://www.cxyxiaowu.com/2176.html
1.3 代碼實作
python版本：
1 # 將arr[l...mid]和arr[mid+1...r]兩部分進行歸并 2 def __merge(nums, left, mid, right): 3 aux = [] 4 for i in range(left, right + 1): 5 aux.append(nums[i]) # 因為這里的aux和nums對應的下標是有一個大小為left的偏移 6 7 # // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1 8 i, j = left, mid + 1 9 for k in range(left, right + 1): 10 if i > mid: # 如果左半部分元素已經全部處理完畢 11 nums[k] = aux[j - left] 12 j += 1 13 elif j > right: # // 如果右半部分元素已經全部處理完畢 14 nums[k] = aux[i - left] 15 i += 1 16 elif aux[i - left] < aux[j - left]: # // 左半部分所指元素 < 右半部分所指元素 17 nums[k] = aux[i - left] 18 i += 1 19 else: # 左半部分所指元素 >= 右半部分所指元素 20 nums[k] = aux[j - left] 21 j += 1 22 23 24 def __merge_sort(nums, left, right): 25 if left >= right: 26 return 27 28 mid = math.floor((left + right) / 2) 29 __merge_sort(nums, left, mid) 30 __merge_sort(nums, mid + 1, right) 31 __merge(nums, left, mid, right) 32 33 34 def merge_sort(nums): 35 __merge_sort(nums, 0, len(nums) - 1)
寫代碼程序中會遇到的兩個小坑：
1.python中“=”只能用來修改list中已有的項，不可以用來增加新的元素那么增加新的元素，有四種方法：append(),extend(),insert(), +加號，不能像下面C++那種寫法，
2.注意python中由于變數宣告不需要指定型別，在遞回中條件涉及除法的時候就要注意強制轉型，防止陷入無窮遞回，
C++版本：
1 // 將arr[l...mid]和arr[mid+1...r]兩部分進行歸并 2 template<typename T> 3 void _merge(T arr[], int l, int mid, int r) { 4 T *aux = new T[r - l + 1]; 5 6 // 兩個陣列之間存在偏移量，需要減去這個偏移，下標才可以正確對應 7 for (int i = l; i <= r; i++) 8 aux[i - l] = arr[i]; 9 10 // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1 11 int i = l; 12 int j = mid + 1; 13 for (int k = l; k <= r; k++) { 14 if (i > mid) { // 如果左半部分元素已經全部處理完畢 15 arr[k] = aux[j - l]; 16 j++; 17 } 18 else if (j > r) { // 如果右半部分元素已經全部處理完畢 19 arr[k] = aux[i - l]; 20 i++; 21 } 22 else if (aux[i - l] < aux[j - l]) { 23 arr[k] = aux[i - l]; 24 i++; 25 } 26 else { // 左半部分所指元素 >= 右半部分所指元素 27 arr[k] = aux[j - l]; 28 j++; 29 } 30 } 31 delete[] aux; 32 } 33 34 template<typename T> 35 void __mergeSort(T arr[], int l, int r) { 36 37 if (l >= r) 38 return; 39 40 int mid = (l + r) / 2; 41 __mergeSort(arr, l, mid); 42 __mergeSort(arr, mid + 1, r); 43 _merge(arr, l, mid, r); 44 } 45 46 // 遞回使用歸并排序,對arr[l...r]的范圍進行排序 47 template<typename T> 48 void mergeSort(T arr[], int n) { 49 __mergeSort(arr, 0, n - 1); 50 }
1.4 歸并排序的改進
當面對近乎有序的陣列，插入排序可以退化成近乎O（n）級別的演算法，此時歸并排序相比插入排序還要慢，
改進1 ：在merge操作前先加入一層判斷， 如果左邊陣列最大值比右邊陣列最小值還要小，那么就說明已經有序，可以跳過merge的操作，
改進2：在遞回到底的情況稍加修改， 當劃分的子陣列小到一定程度時，改而使用插入排序的方法，來加速演算法，這里采用16作為分隔值，
python版本：
1 def insertion_sort(nums, left, right): 2 for i in range(left+1, right+1): 3 pre = i - 1 4 cur_num = nums[i] 5 while pre >= left and nums[pre] > cur_num: 6 nums[pre + 1] = nums[pre] 7 pre -= 1 8 nums[pre + 1] = cur_num 9 10 def __merge_sort(nums, left, right): 11 if right - left <= 15: # 當資料規模很小的時候采用插入排序 12 insertion_sort(nums, left, right) 13 return 14 15 mid = math.floor((left + right) / 2) 16 __merge_sort(nums, left, mid) 17 __merge_sort(nums, mid + 1, right) 18 if nums[mid] > nums[mid + 1]: # 如果已經有序就跳過merge的程序 19 __merge(nums, left, mid, right)
C++版本：
1 template<typename T> 2 void __mergeSort2(T arr[], int l, int r){ 3 4 // 優化2: 對于小規模陣列, 使用插入排序 5 if( r - l <= 15 ){ 6 insertionSort(arr, l, r); 7 return; 8 } 9 10 int mid = (l+r)/2; 11 __mergeSort2(arr, l, mid); 12 __mergeSort2(arr, mid+1, r); 13 14 // 優化1: 對于arr[mid] <= arr[mid+1]的情況,不進行merge 15 // 對于近乎有序的陣列非常有效,但是對于一般情況,有一定的性能損失 16 if( arr[mid] > arr[mid+1] ) 17 __merge(arr, l, mid, r); 18 } 19 20 // 對arr[l...r]范圍的陣列進行插入排序 21 template<typename T> 22 void insertionSort(T arr[], int l, int r){ 23 24 for( int i = l+1 ; i <= r ; i ++ ) { 25 26 T e = arr[i]; 27 int j; 28 for (j = i; j > l && arr[j-1] > e; j--) 29 arr[j] = arr[j-1]; 30 arr[j] = e; 31 } 32 33 return; 34 }
1.5 自底向上的歸并排序
自底向上的排序是歸并排序的一種實作方式，將一個無序的N長陣列切個成N個有序子序列，然后再兩兩合并，然后再將合并后的N/2（或者N/2 + 1）個子序列繼續進行兩兩合并，以此類推得到一個完整的有序陣列，
來張圖幫助理解：
圖源：http://images2015.cnblogs.com/blog/834468/201610/834468-20161016231626327-1390551575.png
代碼實作：
python版本：
1 def merge_sort_bottom_up(nums): 2 length = len(nums) 3 size = 1 4 while size <= length: 5 for i in range(0, length - size, 2 * size): # 這里要保證右邊陣列至少不為空才有意義 6 __merge(nums, i, i + size - 1, min(i + 2 * size - 1, length - 1)) # 這里要保證右邊陣列索引不越界 7 size += size
C++ 版本：
1 template<typename T> 2 void mergeSortBU(T arr[], int n) { 3 4 for (int size = 1; size <= n; size += size) { 5 for (int i = 0; i + size < n; i += 2 * size) //右邊陣列要是不為空的這次歸并才有意義，所以i+size<n 6 __merge(arr, i, i + size - 1, min(i + 2 * size - 1, m - 1)); // 防止右邊陣列的右邊界比陣列比陣列邊界還大， 需要在二者之間取最小值 7 } 8 } 9 10 // merge操作和上述是一樣的，在此就不作贅述
仔細觀察可以發現，自底向上的實作方法中，對陣列的訪問并沒有要用到索引，因此使用這種方法可以以nlog（n）的復雜度對鏈表實作排序！
1.6
- 比較：自頂向下的歸并排序：自頂向下劃分，自底向上歸并， 自頂向下的歸并排序的merge操作可以理解為遞回樹的后序遍歷，
自底向上的歸并排序：底部直接劃分，自底向上歸并
- 歸并的空間復雜度就是那個臨時的陣列和遞回時壓入堆疊的資料占用的空間：n + logn；所以空間復雜度為: O(n)， 空間換時間
- 時間復雜度：O( nlogn )
- 非原地排序
- 穩定排序
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/75819.html
標籤：其他
下一篇：LeetCode：Z 字形變換