?

今天寫一個歸并排序的模板，返回值為該序列的逆序對數

?

基本思路

歸并排序就是利用二分的思想，將區間無限遞歸二分，直到當前劃分區間只包含一個元素或沒有元素的時候（我們認為這個序列是自動有序的），我們回溯到上一層，然后將當前層的左右兩個區間合并為一個有序序列，然后繼續回溯，回溯之后，當前層的左右兩個區間都應該分別是已經經過合并的有序子區間，我們將這兩個有序子區間再進行有序合并，再返回上一層，直到返回最大區間，則合并最大區間的左右有序子區間，得到有序序列。

流程演示

比如：22 ?3 ?1 ?5 ?4 ?7 ?9 ?1 ?8 ?0

紅色區間劃分：22 ?3 ?1 ?5 ?4

左邊：22? ?3 ? ? ? 右邊 ? 1 ? 5 ? 4

左邊：合并有序：3 ? 22

右邊：5 ?4區間遞歸返回時候變為：4 5

右邊合并：1 ?4 ?5

左右區間合并為一個區間：1 ?3 ?4 ?5 ?22

至此左側區間處理完畢

右側區間同理，得到有序序列：0 ?1 ?7 ?8 ?9

最后合并整個區間

0 ?1 ?1 ?3 ?4 ?5 ?7 ?8 ?9 ?22

?

逆序對數

我們利用歸并的思想，它會將每個區間細分到最小，返回整合的時候，會進行左右區間合并，合并的時候就要比較左右區間當前值那個大，然后取小的那個，我們可以在比較的時候做記錄，如果左側的值小于右側，我們就做記錄，這樣一路回溯，就會找到所有的逆序對數。

我們利用歸并排序的返回值來將此記錄值輸出到外部

?

泛型代碼：

template<typename value_type, typename value_Ptr> int merge_sort(const value_Ptr& begin, const value_Ptr& end) {static std::vector<value_type> to(end - begin);static int cnt{ 0 }; //記錄逆序對數if (end - begin <= 1)return 0;value_Ptr mid = begin + (end - begin) / 2;merge_sort<value_type>(begin, mid);merge_sort<value_type>(mid, end);//將上述兩段區間順序排列value_Ptr l = begin, r = mid;int k{ 0 }, index{ 0 };while (l < mid && r < end)if (*l < *r)to[k++] = *l++;else //如果左側值小于右側 {cnt += mid - l; //逆序對數記錄to[k++] = *r++;}while (l < mid)to[k++] = *l++;while (r < end)to[k++] = *r++;for (index = 0; begin + index < end; ++index)*(begin + index) = to[index];return cnt; }

?

測試與使用

#include <iostream> #include <vector>using namespace std;int main() {ios::sync_with_stdio(false);int list[10]{ 22,3,1,5,4,7,9,1,8,0 };vector<int> v{ list,list + 10 };int cnt = merge_sort<int>(list + 0, list + 10);merge_sort<int>(v.begin(), v.end());for (auto it : v)cout << it << " ";cout << endl;for (auto it : list)cout << it << " ";cout << endl;cout << "逆序對數:" << cnt << endl << endl;char list_[10]{ 'r','c','2','A','z','b','8','0','r', '3' };vector<char>v_{ list_,list_ + 10 };cnt = merge_sort<char>(list_ + 0, list_ + 10);merge_sort<char>(v_.begin(), v_.end());for (auto it : v_)cout << it << " ";cout << endl;for (auto it : list_)cout << it << " ";cout << endl;cout << "逆序對數:" << cnt << endl << endl; }

?

?

時間復雜度為：O(N * log N)

?

感謝您的閱讀，生活愉快~

?

轉載于:https://www.cnblogs.com/lv-anchoret/p/9539504.html

總結

以上是生活随笔為你收集整理的泛 归并排序 及 逆序对的全部內容，希望文章能夠幫你解決所遇到的問題。

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