前言
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并?！栋俣劝倏啤?/p>
1. 歸并排序
歸并過程為：比較 a[i] 和 b[j] 的大小，若 a[i] ≤ b[j]，則將第一個(gè)有序表中的元素 a[i] 復(fù)制到 r[k] 中，并令 i 和 k 分別加上 1；否則將第二個(gè)有序表中的元素 b[j] 復(fù)制到 r[k] 中，并令 j 和 k 分別加 上1，如此循環(huán)下去，直到其中一個(gè)有序表取完，然后再將另一個(gè)有序表中剩余的元素復(fù)制到r中從下標(biāo) k 到下標(biāo) t 的單元。歸并排序的算法我們通常用遞歸實(shí)現(xiàn)，先把待排序區(qū)間 [s,t] 以中點(diǎn)二分，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間 [s,t]。
原理：
歸并操作的工作原理如下：
第一步：申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列
第二步：設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
第三步：比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
重復(fù)步驟3直到某一指針超出序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾
總結(jié)：
- 將兩個(gè)已排好序的數(shù)組合并成一個(gè)有序的數(shù)組,稱之為歸并排序
- 步驟：遍歷兩個(gè)數(shù)組，比較它們的值。誰比較小，誰先放入大數(shù)組中，直到數(shù)組遍歷完成
1. 演算歸并排序過程
現(xiàn)在我有兩個(gè)已經(jīng)排好順序的數(shù)組：int[] arr1 = {2, 7, 8}和int[] arr2 = {1, 4, 9}，我還有一個(gè)大數(shù)組來裝載它們int[] arr = new int[6];
1.1 第一輪
那么，我將兩個(gè)數(shù)組的值進(jìn)行比較，誰的值比較小，誰就放入大數(shù)組中！
首先，拿出 arr1[0] 和 arr2[0] 進(jìn)行比較，顯然是 arr2[0] 比較小，因此將 arr2[0] 放入大數(shù)組中，同時(shí) arr2 指針往后一格。
所以，現(xiàn)在目前為止arr = {1}。
1.2 第二輪
隨后，拿 arr1[0] 和 arr2[1] 進(jìn)行比較，顯然是 arr1[0] 比較小，將 arr1[0] 放入大數(shù)組中，同時(shí) arr1 指針往后一格。
所以，現(xiàn)在目前為止arr = {1,2}。
1.3 第三輪
隨后，拿 arr1[1] 和 arr2[1] 進(jìn)行比較，顯然是 arr2[1] 比較小，將 arr2[1] 放入大數(shù)組中，同時(shí) arr2 指針往后一格。
所以，現(xiàn)在目前為止 arr = {1,2,4}。
……..
遍歷到最后，我們會(huì)將兩個(gè)已排好序的數(shù)組變成一個(gè)已排好序的數(shù)組 arr = {1,2,4,7,8,9}。
2. 歸并排序前提分析(分治法)
從上面的演算我們就直到，歸并排序的前提是需要兩個(gè)已經(jīng)排好順序的數(shù)組，那往往不會(huì)有兩個(gè)已經(jīng)排好順序的數(shù)組給我們的呀(一般是雜亂無章的一個(gè)數(shù)組)，那這個(gè)算法是不是很雞肋的呢？？
其實(shí)并不是的，首先假設(shè)題目給出的數(shù)組是這樣子的：int[] arr = {2, 7, 8, 1, 4, 9};
當(dāng)我們要做歸并的時(shí)候就以 arr[3] 也就元素為 1的 那個(gè)地方分開。是然后用一個(gè)指針 L 指向 arr[0]，一個(gè)指針 M 指向 arr[3]，用一個(gè)指針 R 指向 arr5。有了指針的幫助，我們就可以將這個(gè)數(shù)組切割成是兩個(gè)有序的數(shù)組了（操作的方式就可以和上面一樣了）。
可是上面說了，一般給出的是雜亂無章的一個(gè)數(shù)組，現(xiàn)在還是達(dá)不到要求。比如給出的是這樣一個(gè)數(shù)組：int[] arrays = {9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8};
此時(shí)，我們就得用到分治的思想了：
那么我們也可以這樣想將 int[] arr = {2, 7, 8, 1, 4, 9};數(shù)組分隔成一份一份的，arr[0] 它是一個(gè)有序的"數(shù)組"，arr[1] 它也是一個(gè)有序的"數(shù)組"，利用指針 (L,M,R) 又可以像操作兩個(gè)數(shù)組一樣進(jìn)行排序。最終合成{2,7}…….再不斷拆分合并，最后又回到了我們的arr = {1,2,4,7,8,9}，因此歸并排序是可以排序雜亂無章的數(shù)組的。
這就是我們的分治法--->將一個(gè)大問題分成很多個(gè)小問題進(jìn)行解決，最后重新組合起來。
3. 歸并代碼實(shí)現(xiàn)
實(shí)現(xiàn)步驟：
- 拆分
- 合并
/**
* 歸并排序
* 分解待排序的數(shù)組成兩個(gè)各具 n/2 個(gè)元素的子數(shù)組，遞歸調(diào)用歸并排序兩個(gè)子數(shù)組，合并兩個(gè)已排序的子數(shù)組成一個(gè)已排序的數(shù)組
*/
public class MergeSort {
public static void main(String[] args) {
int[] sort = SortManager.sortArr;
int[] temp = new int[sort.length];
mergeSort(sort, temp, 0, sort.length - 1);
for (int i = 0; i < sort.length; i++) {
System.out.println("輸出結(jié)果：" + sort[i]);
}
}
/**
* 歸并排序
*
* @param arrays
* @param L 指向數(shù)組第一個(gè)元素
* @param R 指向數(shù)組最后一個(gè)元素
*/
public static void mergeSort(int[] arrays, int[] temp, int L, int R) {
// 當(dāng)left == right時(shí)，不需要再劃分
if (L < R) {
//取中間的數(shù)，進(jìn)行拆分
int M = (L + R) / 2;
//左邊的數(shù)不斷拆分
mergeSort(arrays, temp, L, M);
//右邊的數(shù)不斷拆分
mergeSort(arrays, temp, M + 1, R);
//合并
merge(arrays, temp, L, M, R);
}
}
/**
* 合并數(shù)組
*
* @param arrays
* @param L 指向數(shù)組第一個(gè)元素
* @param M 指向數(shù)組分隔的元素
* @param R 指向數(shù)組最后的元素
*/
private static void merge(int[] arrays, int[] temp, int L, int M, int R) {
int i = L, j = M + 1;
// arrays數(shù)組的第一個(gè)元素
int k = 0;
//比較這兩個(gè)數(shù)組的值，哪個(gè)小，就往數(shù)組上放
while (i <= M && j <= R) {
temp[k++] = arrays[i] < arrays[j] ? arrays[i++] : arrays[j++];
}
//如果左邊的數(shù)組還沒比較完，右邊的數(shù)都已經(jīng)完了，那么將左邊的數(shù)抄到大數(shù)組中(剩下的都是大數(shù)字)
while (i <= M) {
temp[k++] = arrays[i++];
}
//如果右邊的數(shù)組還沒比較完，左邊的數(shù)都已經(jīng)完了，那么將右邊的數(shù)抄到大數(shù)組中(剩下的都是大數(shù)字)
while (j <= R) {
temp[k++] = arrays[j++];
}
// 把temp數(shù)據(jù)復(fù)制回原數(shù)組
for (i = 0; i < k; i++) {
arrays[L + i] = temp[i];
}
}
}
申明：開始的圖片來源網(wǎng)絡(luò)，侵刪
