「排序」歸併排序和逆序數問題探究

前言

在排序中，我們可能大部分更熟悉冒泡排序、快排之類。對歸併排序可能比較陌生。然而事實上歸併排序也是一種穩定的排序，時間複雜度為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}

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

而遞歸的思想和上面非遞歸肯定不同的，你可以想想非遞歸：我要考慮當前幾個進行歸併，每個開始的頭座標該怎麼表示，還要考慮是否越界等等問題哈，

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

voidmergesort(int[]array,intleft,intright){   intmid=(left+right)/2;//找到中間節點   if(left

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

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

privatestaticvoidmergesort(int[]array,intleft,intright){  intmid=(left+right)/2;  if(left

逆序數

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

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

也就是比如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^)的複雜度算法，而歸併排序滿足，並且每次只和鄰居進行歸併，歸併後該部分有序。

縱觀歸併的每個單過程例如兩個有序序列：假設序列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

結語

至於歸併排序和逆序數就講這麼多了！個人感覺已經盡力講了，如果有錯誤或者不好的地方還請各位指正。如果感覺可以，還請點贊，關注一波哈。

長期奮戰輸出！

閱讀更多 一直碼農一直爽 的文章

關鍵字: 算法 排序 二路