文章目錄

• • 前言
  • 歸并排序(merge sort)
  • 逆序數
  • 結語

微信公眾號：bigsai
數據結構與算法專欄

前言

在排序中，我們可能大部分更熟悉冒泡排序、快排之類。對歸并排序可能比較陌生。然而事實上歸并排序也是一種穩定的排序，時間復雜度為O(nlogn).

歸并排序是基于分治進行歸并的，有二路歸并和多路歸并.我們這里只講二路歸并并且日常用的基本是二路歸并。并且歸并排序的實現方式有遞歸形式和非遞歸形式。要注意其中的區分(思想上沒有大的區別，只是劃分上會有區分后面會對比)。

并且歸并排序很重要的一個應用是求序列中的逆序數個數。當然逆序數也可以用樹狀數組完成，這里就不介紹了。

歸并排序(merge sort)

歸并和快排都是基于分治算法的。分治算法其實應用挺多的，很多分治會用到遞歸，也有很多遞歸實現的算法是分治，但事實上分治和遞歸是兩把事。分治就是分而治之。因為面對排序，如果不采用合理策略。每多一個數就會對整個整體帶來巨大的影響。而分治就是將整個問題可以分解成相似的子問題。子問題的解決要遠遠高效于整個問題的解決，并且子問題的合并并不占用太大資源。

至于歸并的思想是這樣的：

• 第一次：整串先進行劃分成1個一個單獨，第一次是一一(12 34 56---)歸并成若干對，分成若干2個區間.歸并完(xx xx xx xx----)這樣局部有序的序列。
• 第二次就是兩兩歸并成若干四個(1234 5678 ----)每個小局部是有序的。
• 就這樣一直到最后這個串串只剩一個，然而這個耗費的總次數logn。每次操作的時間復雜的又是O(n)。所以總共的時間復雜度為O(nlogn).

對于分治過程你可能了解了，但是這個兩兩merge的過程其實是很重要的。首先我們直到的兩個序列都是有序的。其實思想也很簡單，假設兩個串串為 3 5 7 8和2 6 9 10進行歸并操作。我們需要借助一個額外的數組team[8]將兩個串串有序存進去就行。而流程是這樣的：

非遞歸的歸并
正常歸并的代碼實現都是借助遞歸的。但是也有不借助遞歸的。大部分課本或者考試如果讓你列歸并的序列，那么默認就是非遞歸的，比如一個序列9,2,6,3,8,1,7,4,10,5序列的劃分也是這樣的。

第一次結束： {2,9}{3,6}{1,8}{4,7}{5,10} 第二次結束：{2,3,6,9}{1,4,7,8}{5,10} 第三次結束：{1,2,3,4,6,7,8,9}{5,10} 第四次結束：{1,2,3,4,5,6,7,8,9,10}

遞歸的歸并
在代碼實現上的歸并可能大部分都是遞歸的歸并。并且遞歸和分治整在一起真的是很容易理解。遞歸可以將問題分解成子問題，而這恰恰是分治所需要的手段。而遞歸的一來一回過程的來(分治)回(歸并)，一切都剛剛好。

而遞歸的思想和上面非遞歸肯定不同的，你可以想想非遞歸：我要考慮當前幾個進行歸并，每個開始的頭坐標該怎么表示，還要考慮是否越界等等問題哈，寫起來略麻煩。

而非遞歸它的過程就是局部—>整體的過程，而遞歸是整體—>局部—>整體的過程。
而遞歸實現的歸并的思想：

void mergesort(int[] array, int left, int right) {int mid=(left+right)/2;//找到中間節點if(left<right)//如果不是一個節點就往下遞歸分治{mergesort(array, left, mid);//左區間(包過mid)進行歸并排序mergesort(array, mid+1, right);//右區間進行歸并排序merge(array, left,mid, right);//左右已經有序了，進行合并}}

同樣是9,2,6,3,8,1,7,4,10,5這么一串序列，它的遞歸實現的順序是這樣的(可能部分有點問題，但是還是有助于理解的)：

所以實現一個歸并排序的代碼為：

private static void mergesort(int[] array, int left, int right) {int mid=(left+right)/2;if(left<right){mergesort(array, left, mid);mergesort(array, mid+1, right);merge(array, left,mid, right);}}private static void merge(int[] array, int l, int mid, int r) {int lindex=l;int rindex=mid+1;int team[]=new int[r-l+1];int teamindex=0;while (lindex<=mid&&rindex<=r) {//先左右比較合并if(array[lindex]<=array[rindex]){team[teamindex++]=array[lindex++];}else { team[teamindex++]=array[rindex++];}}while(lindex<=mid)//當一個越界后剩余按序列添加即可{team[teamindex++]=array[lindex++];}while(rindex<=r){team[teamindex++]=array[rindex++];} for(int i=0;i<teamindex;i++){array[l+i]=team[i];}}

逆序數

首先得了解什么是逆序數：

在數組中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對

也就是比如3 2 1.看3 ，有2 1在后面，看2 有1在后面有3個逆序數。
而比如1 2 3的逆序數為0.

在數組中，暴力確實可以求出逆序數，但是暴力之法太復雜，不可取！而有什么好的方法能解決這個問題呢？ 當前序列我可能不知道有多少序列。但是我們直到如果這個序列如果有序那么逆序數就為0.

在看個序列 abcd 3 2 1 efg編程abcd 1 2 3 efg整個序列逆序數減少3個。因為如果不管abcd還是efg和123三個數相對位置沒有變。所以我們是可以通過某種方法確定逆序數對的。

我們就希望能不能有個過程，動態改變如果逆序數發生變化能夠記錄下來？！比如動那么一下能夠知道有沒有改變的。并且這個動不能瞎動，最好是局部的，有序的動。歸并排序就是很適合的一個結構。因為肯定要選個小于O(n²)的復雜度算法，而歸并排序滿足，并且每次只和鄰居進行歸并，歸并后該部分有序。

縱觀歸并的每個單過程例如兩個有序序列：假設序列2 3 6 8 9和序列1 4 7 10 50這個相鄰區域進行歸并。

而縱觀整個歸并排序。變化過程只需要注意一些相對變化即可也就是把每個歸并的過程逆序數發生變化進行累加，那么最終有序的那個序列為止得到的就是整個序列的逆序數！

至于規律，你可以發現每次歸并過程中，當且僅當右側的數提前放到左側，而左側還未放置的個數就是該元素減少的逆序個數！ 這個需要消化一下，而在代碼實現中，需要這樣進行即可！

int value; ------ ----- ------ private static void merge(int[] array, int l, int mid, int r) {int lindex=l;int rindex=mid+1;int team[]=new int[r-l+1];int teamindex=0;while (lindex<=mid&&rindex<=r) {if(array[lindex]<=array[rindex]){team[teamindex++]=array[lindex++];}else { team[teamindex++]=array[rindex++];value+=mid-lindex+1;//加上左側還剩余的}}while(lindex<=mid){team[teamindex++]=array[lindex++];}while(rindex<=r){team[teamindex++]=array[rindex++];} for(int i=0;i<teamindex;i++){array[l+i]=team[i];}}

結語

原創不易，最后我請你幫兩件事幫忙一下:

star支持一下， 您的肯定是我在平臺創作的源源動力。

微信搜索「bigsai」，關注我的公眾號，不僅免費送你電子書，我還會第一時間在公眾號分享知識技術。加我還可拉你進力扣打卡群一起打卡LeetCode。

記得關注、咱們下次再見！

總結

以上是生活随笔為你收集整理的【排序】归并类排序—归并排序(逆序数问题)的全部內容，希望文章能夠幫你解決所遇到的問題。

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