歸并排序

歸并排序是分而治之的排序算法。

劃分步驟很簡單：將當前數組分成兩半(如果N是偶數，則將其完全平等，或者如果N是奇數，則一邊稍大于一個元素)，然后遞歸地對這兩半進行排序。

遞歸寫法

歸并排序遞歸寫法的思想是，設定一個函數，函數實現的目的是「讓int[] arr在L ~ R位置上有序」，處理過程是從L ~ R上找一個中間位置M，遞歸調用該函數，「讓int[] arr的L ~ M上有序，M+1 ~ R上有序」，每一次不能往下遞歸了，便調用歸并的方法將左右兩邊的數組合并成一個數組，到最后整個數組便有序了。

因此，歸并排序使用遞歸方法實現的方法是：「整體是遞歸，左邊排好序+右邊排好序+merge讓整體有序」。

偽代碼理解這一過程：

將每個元素拆分成大小為1的部分

遞歸地合并相鄰的兩個數組分區

??i?=?左側開始項指數?到?右側最后項指數?的遍歷(兩端包括)

????如果左側首值?<=?右側首值

??????拷貝左側首項的值

????否則：?拷貝右側部分首值

將元素拷貝進原來的數組中

代碼實現：

public?class?MergeSort?{

????public?static?void?main(String[]?args)?{
????????int[]?arr?=?{18,?15,?13,?17,?6,?20,?15,?9};
????????System.out.println("排序前："?+?Arrays.toString(arr));
????????mergeSort(arr);
????????System.out.println("排序后："?+?Arrays.toString(arr));
????}

????public?static?void?mergeSort(int[]?arr)?{
????????if?(arr?==?null?||?arr.length?2)?{
????????????return;
????????}
????????process(arr,?0,?arr.length?-?1);
????}

????public?static?void?process(int[]?arr,?int?L,?int?R)?{
????????if?(L?==?R)?{
????????????return;
????????}
????????int?M?=?L?+?((R?-?L)?>>?1);
????????System.out.println("遞歸調用?L--M--R:"?+?L?+?"--"?+?M?+?"--"?+?R);
????????//左邊數組遞歸
????????process(arr,?L,?M);
????????//右邊數組遞歸
????????process(arr,?M?+?1,?R);
????????merge(arr,?L,?M,?R);
????}

????public?static?void?merge(int[]?arr,?int?L,?int?M,?int?R)?{
????????System.out.println("開始歸并?arr["?+?L?+?"~"?+?M?+?"]和arr["?+?(M?+?1)?+?"~"?+?R?+?"]兩部分數組");
????????//申請一個和arr長度一樣的輔助數組
????????int[]?help?=?new?int[R?-?L?+?1];

????????//比較兩組數組，誰小先拷貝誰到輔助數組，拷貝之后移動數組指針
????????//定義數組指針，LP表示左部分數組指針，RP表示右部分數組指針，i表示輔助數組的指針
????????int?LP?=?L;
????????int?RP?=?M?+?1;
????????int?i?=?0;
????????//左右兩邊數組均不能越界
????????while?(LP?<=?M?&&?RP?<=?R)?{
????????????help[i++]?=?arr[LP]?<=?arr[RP]???arr[LP++]?:?arr[RP++];
????????}
????????//任何一邊的數組要越界了，就把該部分的數寫到help數組
????????while?(LP?<=?M)?{
????????????help[i++]?=?arr[LP++];
????????}
????????while?(RP?<=?R)?{
????????????help[i++]?=?arr[RP++];
????????}
????????//寫回到原數組
????????for?(i?=?0;?i?????????????arr[L?+?i]?=?help[i];
????????}
????}
}
?

小技巧：

• 將一個int類型的數乘以2，可以使用位運算<<左移1位
• int類型的數除以2，位運算>>右移1位

別問為什么，問就是位運算就是快！

?

運行結果：

排序前：[18, 15, 13, 17, 6, 20, 15, 9]
遞歸調用?L--M--R:0--3--7
遞歸調用?L--M--R:0--1--3
遞歸調用?L--M--R:0--0--1
開始歸并?arr[0~0]和arr[1~1]兩部分數組
遞歸調用?L--M--R:2--2--3
開始歸并?arr[2~2]和arr[3~3]兩部分數組
開始歸并?arr[0~1]和arr[2~3]兩部分數組
遞歸調用?L--M--R:4--5--7
遞歸調用?L--M--R:4--4--5
開始歸并?arr[4~4]和arr[5~5]兩部分數組
遞歸調用?L--M--R:6--6--7
開始歸并?arr[6~6]和arr[7~7]兩部分數組
開始歸并?arr[4~5]和arr[6~7]兩部分數組
開始歸并?arr[0~3]和arr[4~7]兩部分數組
排序后：[6, 9, 13, 15, 15, 17, 18, 20]

遞歸函數調用過程，我畫了個簡圖以助理解：

遞歸函數調用過程

拿代碼中的數組分析，過程大概就是這樣子滴：

遞歸歸并排序圖解

非遞歸寫法

?

任何遞歸寫法都能轉換成非遞歸寫法。

?

直接上代碼：

public?static?void?mergeSort2(int[]?arr)?{
????if?(arr?==?null?||?arr.length?2)?{
????????return;
????}
????//數組長度
????int?N?=?arr.length;
????//定義每部分參與比較數組的長度，初始長度為1
????int?mergeSize?=?1;
????//只要mergeSize小于N
????while?(mergeSize?????????int?L?=?0;
????????while?(L?????????????int?M?=?L?+?mergeSize?-?1;
????????????if?(M?>=?N)?{
????????????????break;
????????????}
????????????int?R?=?Math.min(M?+?mergeSize,?N?-?1);
????????????merge(arr,?L,?M,?R);
????????????L?=?R?+?1;
????????}
????????//?為什么需要這個？主要是為了防止溢出，int的最大值是21億多(2^31-1)，
????????//?假如此時mergeSize是20億，運行下面mergeSize*2的時候就會溢出
????????if?(mergeSize?>?N?/?2)?{
????????????break;
????????}
????????mergeSize?<<=?1;
????}
}

其中的merge方法，還是前面遞歸方式調用的merge：

public?static?void?merge(int[]?arr,?int?L,?int?M,?int?R)?{
????System.out.println("開始歸并?arr["?+?L?+?"~"?+?M?+?"]和arr["?+?(M?+?1)?+?"~"?+?R?+?"]兩部分數組");
????//申請一個和arr長度一樣的輔助數組
????int[]?help?=?new?int[R?-?L?+?1];

????//比較兩組數組，誰小先拷貝誰到輔助數組，拷貝之后移動數組指針
????//定義數組指針，LP表示左部分數組指針，RP表示右部分數組指針，i表示輔助數組的指針
????int?LP?=?L;
????int?RP?=?M?+?1;
????int?i?=?0;
????//左右兩邊數組均不能越界
????while?(LP?<=?M?&&?RP?<=?R)?{
????????help[i++]?=?arr[LP]?<=?arr[RP]???arr[LP++]?:?arr[RP++];
????}
????//任何一邊的數組要越界了，就把該部分的數寫到help數組
????while?(LP?<=?M)?{
????????help[i++]?=?arr[LP++];
????}
????while?(RP?<=?R)?{
????????help[i++]?=?arr[RP++];
????}
????//寫回到原數組
????for?(i?=?0;?i?????????arr[L?+?i]?=?help[i];
????}
}

運行結果：

排序前：[18, 15, 13, 17, 6, 20, 15, 9]
開始歸并?arr[0~0]和arr[1~1]兩部分數組
開始歸并?arr[2~2]和arr[3~3]兩部分數組
開始歸并?arr[4~4]和arr[5~5]兩部分數組
開始歸并?arr[6~6]和arr[7~7]兩部分數組
開始歸并?arr[0~1]和arr[2~3]兩部分數組
開始歸并?arr[4~5]和arr[6~7]兩部分數組
開始歸并?arr[0~3]和arr[4~7]兩部分數組
排序后：[6, 9, 13, 15, 15, 17, 18, 20]

這里只是歸并排序的非遞歸寫法，思想也是分而治之！關鍵還是merge方法。

針對代碼中的數組int[] arr={18, 15, 13, 17, 6, 20, 15, 9}，其排序過程動圖演示：

歸并排序動態演示

歸并排序的時間復雜度

歸并排序時間復雜度分析

Level 0：2 ^ 0 = 1次調用merge( ) 和 N / 2 ^ 1個元素，時間：O(2 ^ 0 x 2 x N / 2 ^ 1)= O(N)

Level 1：2 ^ 1 = 2次調用 merge( ) 與N / 2 ^ 2個元素，O(2 ^ 1 x 2 x N / 2 ^ 2)= O(N)

Level 2：2 ^ 2 = 4次調用merge( ) 與N / 2 ^ 3個元素，O(2 ^ 2 x 2 x N / 2 ^ 3)= O(N)...

Level(log N)：2 ^(log N-1)(或N / 2)次調用merge( ) )，其中N / 2 ^ log N(或1)個元素，O(N)， 有 log(N) 個層，每層都執行O(N)次工作，因此總體時間復雜度為 「O(NlogN)」。

?

拓展：

遞歸，計算時間復雜度有一個Master公式：形如

「T(N) = a * T(N/b) + O(N^d)」(其中的a、b、d都是常數)

的遞歸函數，可以直接通過Master公式來確定時間復雜度。

• 如果 log(b,a) < d，復雜度為O(N^d)
• 如果 log(b,a) > d，復雜度為O(N^log(b,a))
• 如果 log(b,a) == d，復雜度為O(N^d ?* logN)

我們的歸并排序可以用下面的公式來計算：

T(N) = 2*T(N/2) + O(N^1)

根據master可知推導出時間復雜度為「O(N×logN)」

?

另外，merge過程需要輔助數組，所以額外空間復雜度為O(N)

歸并排序的實質是把比較行為變成了有序信息并傳遞，比O(N^2)的排序快。

歡迎閱讀我的其他Java基礎文章

• 為什么當初不好好學習算法
• 我用線程池ThreadPoolExecutor處理任務和Redis做緩存查詢，將程序效率提升了5倍！
• 從一道面試題進入Java并發新機制---J.U.C
• synchronized底層實現知多少？synchronized加鎖還會升級？
• 你知道Object o = new Object()在內存中占多少字節嗎？
• Java8新特性Stream還有這種操作？
• 終于看懂別人的代碼了！總結Java 8之Lambda表達式的寫法套路

?

看完點贊，養成習慣。

舉手之勞，贊有余香。

?

總結

以上是生活随笔為你收集整理的实现二分归并排序算法_如何实现归并排序？的全部內容，希望文章能夠幫你解決所遇到的問題。

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