1、歸并排序是什么？
歸并排序和快速排序一樣，都采用了分治演算法的思想，時間復雜度都為O[ nlog (n)]，但其空間復雜度更大一點，為O[ log (n)],不過相對的，歸并是一種穩定排序，這一點和快排是不同的，
歸并排序的思想流程:
先分，我們先舉例一個序列 [ 5 6 9 8 7 4 1 2 3 ]，然后把它不斷的二分到序列里只有1個元素時為止，
① [ 5 6 9 8 7 4 1 2 3 ]
/ \
② [ 5 6 9 8 7 ] [ 4 1 2 3]
/ \ / \
③ [ 5 6 9 ] [ 8 7 ] [ 4 1 ] [ 2 3 ]
/ \ / \ / \ / \
④ [ 5 6 ] [ 9 ] [ 8 ] [ 7 ] [ 4 ] [ 1 ] [ 2 ] [ 3 ]
/ \
⑤ [ 5 ] [ 6 ]
上面這樣的操作就相當于分治演算法中的“分”，但是我們只是“分”了，還沒有“治”，所以我們要么做才能才能“治”呢？
其實很簡單，我們只要反過來，從⑤到①逐項把這些小序列兩兩合并成有序的新序列就可以了，
后治：
⑤ [ 5 ] [ 6 ]
\ /
④ [ 5 6 ] [ 9 ] [ 8 ] [ 7 ] [ 4 ] [ 1 ] [ 2 ] [ 3 ]
\ / \ / \ / \ /
③ [5 6 9 ] [ 7 8 ] [ 1 4 ] [ 2 3 ]
\ / \ /
② [ 5 6 7 8 9 ] [ 1 2 3 4 ]
\ /
① [ 1 2 3 4 5 6 7 8 9 ]
動態圖演示：
手撕代碼：
當然，在代碼中，我們把兩個序列合并成一個有序序列的時候，通常需要另外的記憶體空間（即代碼中的reg陣列）來輔助存盤正在排序資料，當一個新序列排序完成后再把它匯入回原來的記憶體空間（即代碼中arr陣列），有些小伙伴們可能不是很理解這句話，那就從去看看一代碼吧，相信你看完代碼后就能明白了！
1 import java.util.Arrays; 2 3 public class Main { 4 5 public static void merge_sort(int[] arr){ 6 //new 一個等大的臨時空陣列，用于排序時快取資料 7 int[] reg = new int[arr.length]; 8 recursive(arr,reg,0,arr.length-1); 9 } 10 11 public static void recursive(int[] arr,int[] reg,int begin,int end){ 12 //若當前序列不足兩個元素時就不必再分了 13 if(end-begin<1){return;} 14 //獲取二分后兩個序列的首尾下標，>>1是右移一位的位操作，比直接除以2要快 15 int left_begin = begin; 16 int left_end = (begin+end)>>1; 17 int right_begin = left_end+1; 18 int right_end = end; 19 20 //遞回呼叫 21 recursive(arr,reg,left_begin,left_end); 22 recursive(arr,reg,right_begin,right_end); 23 24 //獲取臨時陣列的下標指標 25 int pointer = begin; 26 while (left_begin<=left_end&&right_begin<=right_end){//注意細節，賦值后加一 27 if(arr[left_begin]<arr[right_begin]){ 28 reg[pointer] = arr[left_begin]; 29 left_begin++; 30 }else { 31 reg[pointer] = arr[right_begin]; 32 right_begin++; 33 } 34 pointer++; 35 } 36 //上面的回圈跳出后，左右兩個序列中可能還有一個序列的一部分還沒挪到reg上，把它挪過去 37 while (left_begin<=left_end){ 38 reg[pointer] = arr[left_begin]; 39 left_begin++; 40 pointer++; 41 } 42 while (right_begin<=right_end){ 43 reg[pointer] = arr[right_begin]; 44 right_begin++; 45 pointer++; 46 } 47 48 //把reg上排序好的序列挪回到arr上 49 for(int i = begin ; i<=end ; i++){ 50 arr[i] = reg[i]; 51 } 52 } 53 54 public static void main(String[] args) { 55 int[] arr = {2,5,6,7,3,8,1,0,9}; 56 merge_sort(arr); 57 System.out.println(Arrays.toString(arr)); 58 } 59 }
2、關于快排與歸并排序的區別：
之前聽到過不止一位小伙伴說在面試的時候，容易把快排和歸并排序搞混淆了（畢竟都是分治思想），博主覺得呢，如果只是單純的硬記某種排序的話，我不太推薦這么做，我更建議小伙伴們縱向比較比較，你就會發現，快排和歸并排序還是有兩個主要區別的，
第一個區別在于，歸并排序是先分后治，即先把一個大序列拆分成多個小序列再兩兩合一，而快排則是先治再分，即先把一個大序列治理成閾值左邊數全小于右邊的數的狀態，再以閾值為界概念上二分這個序列（關于快排的更多介紹，可以點擊這里看我的另一篇關于快排的博文），
第二個區別在于，歸并排序的二分是折半二分，分出子問題的程序更像是一個完全二叉樹，但是快排的二分并不是折半的，它具有隨機性的閾值影響，這種二分可能一邊內容多一邊內容少，
最后，如果小伙伴覺得這篇博文對你有幫助的話，就點個推薦吧
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/10634.html
標籤：其他
上一篇：JS高級---遍歷DOM樹