1. 歸并排序原理

? ? ? ? 歸并排序（MERARE-SORT）簡(jiǎn)單來說就是將大的序列先視為若干個(gè)比較小的數(shù)組，分成比較小的結(jié)構(gòu)，然后是利用歸并的思想實(shí)現(xiàn)的排序方法，該算法采用經(jīng)典的分治策略（分就是將問題分成一些小的問題分別求解，而治則將分的階段得到的各答案“合”在一起）。

????????歸并排序算法就是應(yīng)用歸并思想的一個(gè)典型例子。在歸并排序中，我們首先將未排序的數(shù)組不斷地劃分成兩個(gè)子數(shù)組，直到子數(shù)組的長(zhǎng)度為1。然后，我們合并子數(shù)組，使得子數(shù)組按照排序規(guī)則排列，最后得到排序完成的數(shù)組。

????????分治法可以看作是"分而治之"的意思，也就是把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，直到最后子問題可以簡(jiǎn)單的直接求解，從而使得原問題的解即子問題的解的合并。

都需要遞歸地解決子問題，并在最后合并子問題的解。

1. 上圖就是將 一個(gè)大的數(shù)組二分成一個(gè)個(gè)小的數(shù)組，知道最后每個(gè)劃分的數(shù)組只有一個(gè)元素的時(shí)候，開始進(jìn)行合并，這種操作就是分階段，可以理解為遞歸拆分子序列的過程，遞歸的深度為logn。
2. 治階段，將兩個(gè)已經(jīng)有序的子序列合并成一個(gè)有序序列。

遍歷時(shí)處理元素的過程：

?總結(jié)歸并排序的思路：

• 首先將原數(shù)組二分的拆分，直到最后問題變成最小的時(shí)候，也就是每個(gè)子數(shù)組只有一個(gè)元素，開始進(jìn)行第二步。
• 將兩個(gè)子數(shù)組合并，按照合并兩個(gè)有序數(shù)組的方式進(jìn)行，按照?qǐng)D中每個(gè)左右子樹從下往上，然后再將左右子樹合并，每個(gè)子樹最后都是一個(gè)有序數(shù)組。

    public static void mergeSort(int[] array, int start, int end, int temp[]){if (start >= end){return;}mergeSort(array, start, (start + end) / 2,temp);mergeSort(array, (start + end) / 2 + 1, end,temp);merge(array, start, end, temp);}public static void merge(int[] array, int start, int end, int[] temp){int middle = (start + end) /2;int left = start;int right = middle + 1;int index = left;//將兩邊的最小元素移到左邊while (left <= middle && right <= end){if (array[left] < array[right]){temp[index++] = array[left++];}else {temp[index++] = array[right++];}}//左端元素遍歷完，依次把右端元素轉(zhuǎn)移過來while (left <= middle){temp[index++] = array[left++];}//左端元素遍歷完，依次把右端元素轉(zhuǎn)移過來while (right <= end){temp[index++] = array[right++];}//將temp中的元素依次轉(zhuǎn)到array中，for (int i = start; i <= end; i++){array[i] = temp[i];}}