內(nèi)容來自尚硅谷Java數(shù)據(jù)結(jié)構(gòu)與java算法（Java數(shù)據(jù)結(jié)構(gòu)與算法）_嗶哩嗶哩_bilibili

寫在前面:本文內(nèi)容大致和原視頻內(nèi)老師的筆記內(nèi)容相同，會(huì)偶爾插入自己的注釋和理解，盡量會(huì)完成作業(yè)

7.10.1歸并排序介紹

歸并排序(MERGE-SORT)是利用歸并的思想實(shí)現(xiàn)的排序方法，該算法采用經(jīng)典的分治(divide-and-conquer)策略（分治法將問題分(divide)成一些小的問題然后遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補(bǔ)"在一起，即分而治之)。

7.10.2歸并排序思想示意圖1-基本思想

說明:

可以看到這種結(jié)構(gòu)很像一棵完全二叉樹，本文的歸并排序我們采用遞歸去實(shí)現(xiàn)(也可采用迭代的方式去實(shí)現(xiàn)）。分階段可以理解為就是遞歸拆分子序列的過程。

7.10.3歸并排序思想示意圖1-合并相鄰的有序子序列

再來看看治階段，我們需要將兩個(gè)已經(jīng)有序的子序列合并成一個(gè)有序序列，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個(gè)已經(jīng)有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]，來看下實(shí)現(xiàn)步驟

7.10.4歸并排序的應(yīng)用實(shí)例

Int[] arr = {8,4,5,7,1,3,6,2} 排序

代碼演示