(二路)歸并排序指的是將兩個順序序列合并成一個順序序列的方法。它是采用分治法的一個典型應用。

如　設有數列初始狀態為：6,202,100,301,38,8,1

第一次歸并后：{6,202},{100,301},{8,38},{1}

第二次歸并后：{6,100,202,301}，{1,8,38}

第三次歸并后：{1,6,8,38,100,202,301}

歸并排序時間復雜度為o(nlogn)，空間復雜度為o(n)，是一種穩定的排序方法。

完整代碼如下：

#include<iostream>#define N 20void mergeSort(int* arr, int s,int t);void merge(int* arr, int s, int m,int t);int temp[N];//備用數組tempint main(){int a[N] = { 3, 2, 4, 6, 7, 5, 18, 9, 0, 1,16, 8, 20, 33, 28, 64, 19, 31, 30, 25 };for (int i = 0; i <N; i++){std::cout << a[i] << " ";}std::cout << '\n'; mergeSort(a,0,N-1);for (int i = 0; i <N; i++){std::cout << a[i] << " ";}std::cout << '\n';return 0;}void mergeSort(int* arr, int s, int t){if (s < t){int m = (s + t) / 2;mergeSort(arr, s, m);mergeSort(arr, m + 1, t);merge(arr, s, m, t);}}void merge(int* arr, int s, int m, int t){int i, j;//i表示在temp中的下標，下面初始化為0；j表示后半部分起始下標；int start = s;//start保留arr數組中歸并的其實位置，方便后面copy；for (j = m + 1,i=0; j <= t&&s<= m;++i){if (arr[s] < arr[j])//保證排序的穩定性（不能寫成arr[s]>arr[j])temp[i] = arr[s++];elsetemp[i] = arr[j++];}while (s <= m)temp[i++] = arr[s++];while (j<=t)temp[i++] = arr[j++];i = 0;while (start <= t)//copy排好序的數。arr[start++] = temp[i++];}

?

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的归并排序之——二路归并（c/c++）的全部內容，希望文章能夠幫你解決所遇到的問題。

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