歸并排序（merge sort）是一個時間復雜度為O（nlogn）的基于比較的排序算法（comparison based sorting algorithm）。 歸并排序大多數實現（implementation）都將其實現成了一個stable sort, 所謂的stable sort的意思就是the implementation preserves the input order of equal elements in the sorted order。

merge sort 也采用了divide and conquer(分治技術） 的排序算法。 由John von Neumann于1945年發明的。?

我們知道， 快排序的平均情況下時間復雜度是O（nlogn）, 最壞情況下為O（n^2）。 歸并排序的好處就是時間復雜度總是O（nlogn）.。 所以歸并排序在時間方面可以beats quick sort。

下面對merge sort做出詳細說明：

例如， 我們想要對如下數組精心排序：

merge sort 的思想是將一個problem break into 2 subproblems。?

（1）divide the array into 2 equal halves(假如分隔位置在數組的中間（記為mid位置）， mid 之前為the first subarray, 之后為the second subarray):

(2) 現在假如我們somehow 將這兩個子數組排好序了， 接下來我們的任務就是將這兩個子數組merge稱為一個大的排好序的數組。 注意這三個數組時獨立位于內存之中的（可見merge sort 的空間復雜度會比較大）。

我們的merge算法如下。 現在我們將上圖左邊的數組記為L， 右邊的數組記為R。 ?首先第一步，比較L的第一個未選中的數據和R中第一個未選中的數據， 找出最小的數據， 為位于L中的1. 我們將這個值放在A中。 然后移動L的索引到下一個元素2， R的索引記錄不懂， 比較， 發現2大， 將2 放到A的第二個位置。 在移動L中的索引， 到達4， R的不動， 4 比3大， 所以將3 放在A的第三個位置， 移動R的索引記錄到下一個元素。 以此類推， 直至R（或者L）的元素均位于A中， 然后將L（或者R）剩余的元素均拷貝到A中。 即完成排序。

上述算法的偽代碼如下：

現在我們說說如何排序。

解決辦法是我們可以進一步的將數組或者list 進行進一步的細分：

到達最后一步的時候， 然后開始從下網上歸并（merge）。

最終結果如下：

歸并排序的偽代碼如下：

程序如下：

/* Merge sort in C++ */ #include <cstdio> #include <iostream>using namespace std;// Function to Merge Arrays L and R into A. // lefCount = number of elements in L // rightCount = number of elements in R. void Merge(int *A,int *L,int leftCount,int *R,int rightCount) {int i,j,k;// i - to mark the index of left aubarray (L)// j - to mark the index of right sub-raay (R)// k - to mark the index of merged subarray (A)i = 0; j = 0; k =0;while(i<leftCount && j< rightCount) {if(L[i] < R[j]) A[k++] = L[i++];else A[k++] = R[j++];}while(i < leftCount) A[k++] = L[i++];while(j < rightCount) A[k++] = R[j++]; }// Recursive function to sort an array of integers. void MergeSort(int *A,int n) {int mid,i, *L, *R;if(n < 2) return; // base condition. If the array has less than two element, do nothing.mid = n/2; // find the mid index.// create left and right subarrays// mid elements (from index 0 till mid-1) should be part of left sub-array// and (n-mid) elements (from mid to n-1) will be part of right sub-arrayL = new int[mid];R = new int [n - mid];for(i = 0;i<mid;i++) L[i] = A[i]; // creating left subarrayfor(i = mid;i<n;i++) R[i-mid] = A[i]; // creating right subarrayMergeSort(L,mid); // sorting the left subarrayMergeSort(R,n-mid); // sorting the right subarrayMerge(A,L,mid,R,n-mid); // Merging L and R into A as sorted list.// the delete operations is very importantdelete [] R;delete [] L; }int main() {/* Code to test the MergeSort function. */int A[] = {6,2,3,1,9,10,15,13,12,17}; // creating an array of integers.int i,numberOfElements;// finding number of elements in array as size of complete array in bytes divided by size of integer in bytes.// This won't work if array is passed to the function because array// is always passed by reference through a pointer. So sizeOf function will give size of pointer and not the array.// Watch this video to understand this concept - http://www.youtube.com/watch?v=CpjVucvAc3gnumberOfElements = sizeof(A)/sizeof(A[0]);// Calling merge sort to sort the array.MergeSort(A,numberOfElements);//printing all elements in the array once its sorted.for(i = 0;i < numberOfElements;i++)cout << " " << A[i];return 0; }

運行結果為：

NOTE： 在code：：blocks 下可以調試， 單步運行， 打開watches 窗口查看各個變量

也可以查看call stack:

總結

以上是生活随笔為你收集整理的C++ Merge sort(归并排序)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。