歸并排序算法 · Programiz 中文系列教程

# 歸并排序算法 > 原文： [https://www.programiz.com/dsa/merge-sort](https://www.programiz.com/dsa/merge-sort) #### 在本教程中，您將學習歸并排序。此外，您還將找到合并類別 C，C++ ，Java 和 Python 的工作示例。歸并排序是計算機編程中的一種“分治”算法。它是最流行的排序算法之一，也是建立對構建遞歸算法的信心的一種好方法。 ![merge sort example](https://img.kancloud.cn/40/e3/40e3938a7d34caab750ad089abed121f_1212x1232.png "Merge sort example") 歸并排序示例 * * * ## 分治策略使用[分治技術](/dsa/divide-and-conquer)，我們將一個問題分為多個子問題。準備好每個子問題的解決方案后，我們將這些子問題的結果“組合”起來以解決主要問題。假設我們必須對數組`A`進行排序。一個子問題將是對該數組的一個子節進行排序，該子節開始于索引`p`，結束于索引`r`，表示為`A[p..r]`。 **劃分** 如果`q`是`p`和`r`之間的中點，則我們可以將子數組`A[p..r]`分成兩個數組`A[p..q]`和`A[q + 1..r]`。 **解決** 在解決步驟中，我們嘗試對兩個子數組`A[p..q]`和`A[q + 1..r]`進行排序。如果尚未達到基本情況，則再次劃分這兩個子數組，然后嘗試對它們進行排序。 **合并** 當解決步驟到達基本步驟時，我們得到`A[p..r]`數組的兩個排序的子數組`A[p..q]`和`A[q + 1..r]`，我們通過從兩個排序的子數組`A[p]`創建一個排序的數組`A[p..r]`來組合結果`A[p..q]`和`A[q + 1..r]`。 * * * ## 歸并排序算法歸并排序函數將數組重復分成兩半，直到我們達到對大小為 1 的子數組（即`p == r`）執行歸并排序的階段。之后，合并函數開始起作用，并將排序后的數組合并為更大的數組，直到合并整個數組。 ``` MergeSort(A, p, r): if p > r return q = (p+r)/2 mergeSort(A, p, q) mergeSort(A, q+1, r) merge(A, p, q, r) ``` 要對整個數組進行排序，我們需要調用`MergeSort(A, 0, length(A)-1)`。如下圖所示，歸并排序算法將數組遞歸地分成兩半，直到我們得到具有 1 個元素的數組的基本情況。之后，合并函數將拾取排序后的子數組并將其合并以逐漸對整個數組進行排序。 ![merge sort algorithm visualization](https://img.kancloud.cn/e9/68/e968527c5b205ba759f5a1b6ab6f9e6a_1246x770.png "Merge sort in action") 歸并排序實戰 ### 合并步驟每個遞歸算法都依賴于基本情況以及將基本情況的結果進行組合的能力。歸并排序沒有什么不同。您猜對了，歸并排序算法最重要的部分是合并步驟。合并步驟是解決合并兩個排序列表（數組）以構建一個大排序列表（數組）這一簡單問題的解決方案。該算法維護三個指針，一個用于兩個數組中的每個，另一個用于維護最終排序后的數組的當前索引。 ``` Have we reached the end of any of the arrays? No: Compare current elements of both arrays Copy smaller element into sorted array Move pointer of element containing smaller element Yes: Copy all remaining elements of non-empty array ``` ![merge two sorted arrays](https://img.kancloud.cn/7c/c8/7cc8699c0d982e879a09cf4fd810468d_1310x1160.png "Merge step") 合并步驟 * * * ## 編寫合并算法代碼我們上面描述的合并步驟和用于歸并排序的步驟之間的明顯區別是，我們僅對連續的子數組執行合并函數。這就是為什么我們只需要數組，第一個位置，第一個子數組的最后一個索引（我們可以計算第二個子數組的第一個索引）和第二個子數組的最后一個索引的原因。我們的任務是合并兩個子數組`A[p..q]`和`A[q + 1..r]`，以創建排序數組`A[p..r]`。因此，函數的輸入為`A`，`p`，`q`和`r` 合并函數的工作方式如下： 1. 創建子數組`L ← A[p..q]`和`M←A[q + 1..r]`的副本。 2. 創建三個指針`i`，`j`和`k` 1. `i`維持`L`的當前索引，從 1 開始 2. `j`維持`M`的當前索引，從 1 開始 3. `k`維持`A[p..q]`的當前索引，從`p`開始。 3. 直到我們到達`L`或`M`的末尾，再從`L`和`M`中選擇較大的元素，然后將它們放在`A[p..q]`的正確位置 4. 當我們用盡`L`或`M`中的元素時，請拾取其余元素，然后放入`A[p..q]` 在代碼中，這看起來像： ``` // Merge two subarrays L and M into arr void merge(int arr[], int p, int q, int r) { // Create L ← A[p..q] and M ← A[q+1..r] int n1 = q - p + 1; int n2 = r - q; int L[n1], M[n2]; for (int i = 0; i < n1; i++) L[i] = arr[p + i]; for (int j = 0; j < n2; j++) M[j] = arr[q + 1 + j]; // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A[p..r] while (i < n1 && j < n2) { if (L[i] <= M[j]) { arr[k] = L[i]; i++; } else { arr[k] = M[j]; j++; } k++; } // When we run out of elements in either L or M, // pick up the remaining elements and put in A[p..r] while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = M[j]; j++; k++; } } ``` * * * ## `Merge()`函數逐步解釋這個函數發生了很多事情，所以讓我們舉個例子來看一下它是如何工作的。和往常一樣，一張圖片說出一千個單詞。 ![Merging two consecutive subarrays of array](https://img.kancloud.cn/40/d4/40d4e0751fee3b9dc640cefcb44e170a_670x224.png "Merging two consecutive subarrays of array") 合并數組的兩個連續子數組數組`A[0..5]`包含兩個排序的子數組`A[0..3]`和`A[4..5]`。讓我們看看`merge`函數如何合并兩個數組。 ``` void merge(int arr[], int p, int q, int r) { // Here, p = 0, q = 4, r = 5 (size of array) ``` ### 步驟 1：創建要排序的子數組的重復副本 ``` // Create L ← A[p..q] and M ← A[q+1..r] int n1 = q - p + 1 = 3 - 0 + 1 = 4; int n2 = r - q = 5 - 3 = 2; int L[4], M[2]; for (int i = 0; i < 4; i++) L[i] = arr[p + i]; // L[0,1,2,3] = A[0,1,2,3] = [1,5,10,12] for (int j = 0; j < 2; j++) M[j] = arr[q + 1 + j]; // M[0,1,2,3] = A[4,5] = [6,9] ``` ![Create copies of subarrays for merging](https://img.kancloud.cn/53/66/5366d2c341c1cb1251857cfea58ba34a_622x400.png "Create copies of subarrays for merging") 創建子數組的副本以進行合并 ### 步驟 2：維護子數組和主數組的當前索引 ``` int i, j, k; i = 0; j = 0; k = p; ``` ![Maintain indices of copies of sub array and main array](https://img.kancloud.cn/4f/c8/4fc82b8ea3cdbdfcc3ded5b350267398_1292x316.png "Merge Sort") 維護子數組和主數組副本的索引 ### 步驟 3：直到我們到達`L`或`M`的盡頭，在元素`L`和`M`中選擇更大的一個，并將其放置在`A[p..r]`的正確位置 ``` while (i < n1 && j < n2) { if (L[i] <= M[j]) { arr[k] = L[i]; i++; } else { arr[k] = M[j]; j++; } k++; } ``` ![Comparing individual elements of sorted subarrays until we reach end of one](https://img.kancloud.cn/9b/fc/9bfcf67152177b9064c907743a1f961d_1310x1178.png "Merge sort") 比較排序的子數組的各個元素，直到我們到達一個的結尾 ### 步驟 4：當我們用完`L`或`M`中的元素時，請選取剩余的元素并放入`A[p..r]` ``` // We exited the earlier loop because j < n2 doesn't hold while (i < n1) { arr[k] = L[i]; i++; k++; } ``` ![Copy the remaining elements from the first array to main subarray](https://img.kancloud.cn/54/53/545376e3864cbfe6206ad697da9068d4_1104x720.png "Merge Sort") 將其余元素從第一個子數組復制到主數組 ``` // We exited the earlier loop because i < n1 doesn't hold while (j < n2) { arr[k] = M[j]; j++; k++; } } ``` ![Copy remaining elements of second array to main subarray](https://img.kancloud.cn/9f/8f/9f8f56afba081c0fa3804d32edb73d3e_946x316.png "Merge Sort") 將其余元素從第二個子數組復制到主數組如果`M`的大小大于`L`，則需要此步驟。在合并函數的末尾，對子數組`A[p..r]`進行排序。 * * * ## Python，Java 和 C/C++ 示例 ```py # MergeSort in Python def mergeSort(array): if len(array) > 1: # r is the point where the array is divided into two subarrays r = len(array)//2 L = array[:r] M = array[r:] # Sort the two halves mergeSort(L) mergeSort(M) i = j = k = 0 # Until we reach either end of either L or M, pick larger among # elements L and M and place them in the correct position at A[p..r] while i < len(L) and j < len(M): if L[i] < M[j]: array[k] = L[i] i += 1 else: array[k] = M[j] j += 1 k += 1 # When we run out of elements in either L or M, # pick up the remaining elements and put in A[p..r] while i < len(L): array[k] = L[i] i += 1 k += 1 while j < len(M): array[k] = M[j] j += 1 k += 1 # Print the array def printList(array): for i in range(len(array)): print(array[i], end=" ") print() # Driver program if __name__ == '__main__': array = [6, 5, 12, 10, 9, 1] mergeSort(array) print("Sorted array is: ") printList(array) ``` ```java // Merge sort in Java class MergeSort { // Merge two subarrays L and M into arr void merge(int arr[], int p, int q, int r) { // Create L ← A[p..q] and M ← A[q+1..r] int n1 = q - p + 1; int n2 = r - q; int L[] = new int[n1]; int M[] = new int[n2]; for (int i = 0; i < n1; i++) L[i] = arr[p + i]; for (int j = 0; j < n2; j++) M[j] = arr[q + 1 + j]; // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A[p..r] while (i < n1 && j < n2) { if (L[i] <= M[j]) { arr[k] = L[i]; i++; } else { arr[k] = M[j]; j++; } k++; } // When we run out of elements in either L or M, // pick up the remaining elements and put in A[p..r] while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = M[j]; j++; k++; } } // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr[], int l, int r) { if (l < r) { // m is the point where the array is divided into two subarrays int m = (l + r) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); } } // Print the array static void printArray(int arr[]) { int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr[i] + " "); System.out.println(); } // Driver program public static void main(String args[]) { int arr[] = { 6, 5, 12, 10, 9, 1 }; MergeSort ob = new MergeSort(); ob.mergeSort(arr, 0, arr.length - 1); System.out.println("Sorted array:"); printArray(arr); } } ``` ```c // Merge sort in C #include <stdio.h> // Merge two subarrays L and M into arr void merge(int arr[], int p, int q, int r) { // Create L ← A[p..q] and M ← A[q+1..r] int n1 = q - p + 1; int n2 = r - q; int L[n1], M[n2]; for (int i = 0; i < n1; i++) L[i] = arr[p + i]; for (int j = 0; j < n2; j++) M[j] = arr[q + 1 + j]; // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A[p..r] while (i < n1 && j < n2) { if (L[i] <= M[j]) { arr[k] = L[i]; i++; } else { arr[k] = M[j]; j++; } k++; } // When we run out of elements in either L or M, // pick up the remaining elements and put in A[p..r] while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = M[j]; j++; k++; } } // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr[], int l, int r) { if (l < r) { // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); } } // Print the array void printArray(int arr[], int size) { for (int i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n"); } // Driver program int main() { int arr[] = {6, 5, 12, 10, 9, 1}; int size = sizeof(arr) / sizeof(arr[0]); mergeSort(arr, 0, size - 1); printf("Sorted array: \n"); printArray(arr, size); } ``` ```cpp // Merge sort in C++ #include <iostream> using namespace std; // Merge two subarrays L and M into arr void merge(int arr[], int p, int q, int r) { // Create L ← A[p..q] and M ← A[q+1..r] int n1 = q - p + 1; int n2 = r - q; int L[n1], M[n2]; for (int i = 0; i < n1; i++) L[i] = arr[p + i]; for (int j = 0; j < n2; j++) M[j] = arr[q + 1 + j]; // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A[p..r] while (i < n1 && j < n2) { if (L[i] <= M[j]) { arr[k] = L[i]; i++; } else { arr[k] = M[j]; j++; } k++; } // When we run out of elements in either L or M, // pick up the remaining elements and put in A[p..r] while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = M[j]; j++; k++; } } // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr[], int l, int r) { if (l < r) { // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); } } // Print the array void printArray(int arr[], int size) { for (int i = 0; i < size; i++) cout << arr[i] << " "; cout << endl; } // Driver program int main() { int arr[] = {6, 5, 12, 10, 9, 1}; int size = sizeof(arr) / sizeof(arr[0]); mergeSort(arr, 0, size - 1); cout << "Sorted array: \n"; printArray(arr, size); return 0; } ``` * * * ## 歸并排序復雜度 ### 時間復雜度最佳情況復雜度：`O(n * log n)` 最壞情況的復雜度：`O(n * log n)` 平均情況復雜度：`O(n * log n)` ### 空間復雜度歸并排序的空間復雜度為`O(n)`。 * * * ## 歸并排序應用 * 倒數問題 * 外部排序 * 電子商務應用