看圖輕鬆理解資料結構與算法系列(合併排序)
推出一個新系列，《看圖輕鬆理解資料結構和演算法》，主要使用圖片來描述常見的資料結構和演算法，輕鬆閱讀並理解掌握。本系列包括各種堆、各種佇列、各種列表、各種樹、各種圖、各種排序等等幾十篇的樣子。
合併排序
合併排序也叫歸併排序，它的主要思想是分治法，把待排序序列分為若干有序子序列，然後將兩個或兩個以上的有序子序列進行合併，得到一個新的完整的有序序列。所以首先得先對子序列進行排序，得到有序子序列，然後再使序列段之間有序。
排序要點
既然是分治法，那麼就涉及到分和治。分，即遞迴地將序列分成小序列再求解；治，即遞迴地將分成的小序列合併到一起。
- 設序列長度為L，將序列分為兩個長度為(L/2)的子序列。
- 繼續遞迴地對兩個子序列分割，直至不能再繼續分割，此時每個子序列只有一個元素。
- 對分割後的子序列進行遞迴地合併，按一定順序組合成有序子序列，有序子序列之間繼續合併。
- 最終合併成一個完整的長度為L的有序序列。
排序過程
假設我們有如下8個元素，分別為 84,25,59,71,62,16,34,45 ，現在進行合併排序。
先將0到3分為子序列，4到7分為子序列，
對於0到3子序列，繼續分為0到1的子序列，2到3的子序列，
對於0到1子序列，繼續分為0子序列和1子序列，然後對這兩個子序列進行合併，兩個子序列都只有一個元素，一個元素的序列可以看成是有序序列，我們把它們合併成有序序列，25小，先提出來，
然後是84，
排好序的序列放回原來序列中，於是完成0和1子序列的合併操作，01變成有序子序列。接著處理2子序列和3子序列，
59比較小，先提出來，
然後是71，
排好序的序列放回原來序列中，於是完成2和3子序列的合併操作，23變成有序子序列。
接下去開始合併01有序子序列和23有序子序列，01序列中最小的元素25小於23序列中最小的元素59，於是25先提出來，
01序列剩餘元素中最小元素84大於23序列中最小的元素59，於是59提出來，
84與71比較，提出71，
最後提出84，
於是完成0到3的合併，0到3變為有序序列，放回原序列中。接下去處理4到7的子序列，
繼續分為4到5的子序列，6到7的子序列，
對於45子序列，繼續分為4子序列和5子序列，然後對這兩個子序列進行合併，兩個子序列都只有一個元素，一個元素的序列可以看成是有序序列，我們把它們合併成有序序列，16小，先提出來，
然後是62，
排好序的序列放回原來序列中，於是完成4和5子序列的合併操作，45變成有序子序列。接著處理6子序列和7子序列，
34較小，先提出來，
然後是45，
排好序的序列放回原來序列中，於是完成6和7子序列的合併操作，67變成有序子序列。
接下去開始合併45有序子序列和67有序子序列，45序列中最小的元素16小於67序列中最小的元素34，於是16先提出來，
45序列中剩餘元素中最小元素62大於67序列中最小的元素34，於是34提出來，
62與45比較，提出45，
最後提出62，
於是完成4到7的合併，4到7變為有序序列，放回原序列中。現在我們已經完成了0到3的有序序列和4到7的有序序列，接下去開始合併03序列和47序列，
03序列最小元素25與47序列最小元素16比較，選出小的16，
繼續比較兩個序列最小的元素，25與34比較，選出25，
接著59與34比較，選出34，
59與45比較，選出45，
59與62比較，選出59，
71與62比較，選出62，
然後剩下的71和84不用比較了，因為47序列已經沒有元素了，直接按照原來順序提出來即可，
最終完成排序。
-------------推薦閱讀------------
ofollow,noindex">我的開源專案彙總(機器&深度學習、NLP、網路IO、AIML、mysql協議、chatbot)
我的2017文章彙總——Java及中介軟體
我的2017文章彙總——JDK原始碼篇
跟我交流，向我提問：
Line"/>
歡迎關注：
