簡(jiǎn)單介紹
歸并排序（merge sort）是利用 歸并 的思想實(shí)現(xiàn)的排序方法，該算法采用經(jīng)典的分治(divide-and-conquer)策略 ：
- 分（divide）：將問題分成一些小的問題，然后遞歸求解
- 治（conquer）：將分的階段得到的各答案「修補(bǔ)」在一起
即：分而治之
該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。
基本思想
- 分：分的過程只是為了分解
- 治：分組完成后，開始對(duì)每組進(jìn)行排序，然后合并成一個(gè)有序序列，直到最后將所有分組合并成一個(gè)有序序列
可以看到這種結(jié)構(gòu)很像一棵完全二叉樹，本文的歸并排序我們采用遞歸實(shí)現(xiàn)（也可采用迭代的方式實(shí)現(xiàn)）。分階段可以理解為就是遞歸拆分子序列的過程。
注：這些數(shù)從始至終都在一個(gè)數(shù)組里（只是抽象的想想成兩個(gè)數(shù)組），除了排序時(shí)會(huì)把要排序的數(shù)copy到一個(gè)臨時(shí)數(shù)組里面，這里如果不懂后面看了代碼后，再返回來思考就懂了。一定要思考！?。?！
下面的動(dòng)圖可以很直觀的看到整個(gè)算法實(shí)現(xiàn)的過程，初體驗(yàn)一下吧，后面的代碼可以結(jié)合上面的圖，和這個(gè)動(dòng)圖，來整理一下邏輯
多個(gè)數(shù)排序動(dòng)圖：
思路分析
對(duì)于分階段相對(duì)較簡(jiǎn)單，下面著重來對(duì)治階段進(jìn)行分析。
合并相鄰有序子序列分析：下圖以 歸并排序的最后一次合并 為例來分析，即對(duì)應(yīng)上圖的 [4,5,7,8] 和 [1,2,3,6] 兩個(gè)已經(jīng)有序的子序列合并為最終序列 [1,2,3,4,5,6,7,8]，下圖展示了實(shí)現(xiàn)步驟
如圖所示：這是最后一次的合并 操作，是兩個(gè)有序序列合并為最終的有序序列。
-
1.從有序序列開始挨個(gè)比較，這里比較 4 和 1，1 < 4，那么 1 進(jìn)入臨時(shí)數(shù)組
temp中，并且將自己的指針右移動(dòng)一位 - 2.由于圖上綠色部分上一次 4 大于 1，指針并未移動(dòng)，然后 4 和 2 對(duì)比，2 < 4 , 2 進(jìn)入到臨時(shí)數(shù)組中，并且將自己的指針右移動(dòng)一位
- 3. ...
- 4.如果某一組已經(jīng)全部進(jìn)入了臨時(shí)數(shù)組，那么剩余一組的剩余有序序列直接追加到臨時(shí)數(shù)組中
- 5.最后，將 temp 內(nèi)容拷貝到原數(shù)組中去，完成排序
代碼實(shí)現(xiàn)
先實(shí)現(xiàn)合并方法，這個(gè)是該算法中最重要的，你也看可以直接看后面的完整算法代碼，再返回來思考，這個(gè)都隨你。此次是因?yàn)?分 的步驟需要用到 合 的這個(gè)，所以我這里就先放 合并的代碼了。
/**
*
* 最難的是合并,所以可以先完成合并的方法，此方法請(qǐng)參考 基本思想 和 思路分析中的圖解來完成
* 動(dòng)腦筋
*
*
*
* @param arr 要排序的原始數(shù)組
* @param left 因?yàn)槭呛喜?，所以要得到左右兩邊的的?shù)組信息，這個(gè)是左側(cè)數(shù)組的第一個(gè)索引值
* @param mid 因?yàn)槭且粋€(gè)數(shù)組，標(biāo)識(shí)是第一個(gè)數(shù)組的最后一個(gè)索引，即 mid+1 是右側(cè)數(shù)組的第一個(gè)索引，即中間索引
* @param right 右側(cè)數(shù)組的結(jié)束索引，右邊數(shù)組的最后一個(gè)數(shù)
* @param temp 臨時(shí)空間，臨時(shí)數(shù)組
*/
public void merge(int[] arr, int left, int mid, int right, int[] temp) {
// 定時(shí)臨時(shí)變量，用來遍歷數(shù)組比較
int l = left; // 左邊有序數(shù)組的初始索引
int r = mid + 1; // 右邊有序數(shù)組的初始索引
int t = 0; // temp 數(shù)組中當(dāng)前最后一個(gè)有效數(shù)據(jù)的索引
// 1. 按思路先將兩個(gè)數(shù)組（有序的）有序的合并到 temp 中
// 因?yàn)槭呛喜蓚€(gè)數(shù)組，所以需要兩邊的數(shù)組都還有值的時(shí)候才能進(jìn)行 比較合并
// 若其中一個(gè)數(shù)組的值遍歷完了（取完了），那么就跳出該循環(huán)，把另一個(gè)數(shù)組所剩的值，直接copy進(jìn)臨時(shí)數(shù)組即可
while (l <= mid && r <= right) {
// 如果左邊的比右邊的小，則將左邊的該元素填充到 temp 中
// 并移動(dòng) t++,l++,好繼續(xù)下一個(gè)
if (arr[l] < arr[r]) {
temp[t] = arr[l];
t++;//移動(dòng) temp 臨時(shí)數(shù)組中當(dāng)前最后一個(gè)有效數(shù)據(jù)的索引
l++; //左邊原始數(shù)組的索引移動(dòng)
}
// 否則則將右邊的移動(dòng)到 temp 中
else {
temp[t] = arr[r];
t++;//移動(dòng) temp 臨時(shí)數(shù)組中當(dāng)前最后一個(gè)有效數(shù)據(jù)的索引
r++;//右邊原始數(shù)組的索引移動(dòng)
}
}
// 2. 如果有任意一邊的數(shù)組還有值，則依序?qū)⑹Ｓ鄶?shù)據(jù)填充到 temp 中
// 如果左側(cè)還有值
while (l <= mid) {
temp[t] = arr[l];
t++;
l++;
}
// 如果右側(cè)還有值
while (r <= right) {
temp[t] = arr[r];
t++;
r++;
}
// 3. 將 temp 數(shù)組，拷貝到原始數(shù)組
// 注意：只拷貝當(dāng)前temp有效數(shù)據(jù)到對(duì)應(yīng)的原始數(shù)據(jù)中，通俗點(diǎn)說，就是原始數(shù)組中要排序的數(shù)據(jù)，通過temp排成了有序的，然后將temp中的有序數(shù)據(jù)將原始數(shù)組中原來要排序的那部分覆蓋了就行了
int tempL = left; // 從左邊開始拷貝，左邊第一個(gè)值的索引
t = 0; // temp 中的有效值索引，有效值邊界可以通過 right 判定，因?yàn)楹喜蓚€(gè)數(shù)組到 temp 中，邊界就是 right ，這里自己好好想想
/*
* 對(duì)于 8,4,5,7,1,3,6,2 這個(gè)數(shù)組,
* 從棧頂開始合并：8,4 | 5,7 1,3 | 6,2
* 先左遞歸的話：
* 第一次：8,4 合并：tempL=0，right=1
* 第二次：5,7 合并：tempL=2，right=3
* 第三次：4,8 | 5，7 進(jìn)行合并，tempL=0，right=3
* 直到左遞歸完成，得到左側(cè)一個(gè)有序的序列：4,5,7,8 然后再開始遞歸右邊那個(gè)無序的
* 最后回到棧底分解成兩個(gè)數(shù)組的地方，將兩個(gè)數(shù)組合并成一個(gè)有序數(shù)組
* 這里真的得自己想了，我只能這么說了。
*/
System.out.println("tempL=" + tempL + "; right=" + right);
while (tempL <= right) {
arr[tempL] = temp[t];
tempL++;
t++;
}
}
需要注意的是：這個(gè)圖一定要看明白：
- 1.一直分解，到棧頂首次合并時(shí)，是兩個(gè)數(shù)字，也就是說，左側(cè)數(shù)組只有一個(gè)數(shù)字，右側(cè)數(shù)組只有一個(gè)數(shù)字
-
2.左側(cè)數(shù)組只有一個(gè)數(shù)字時(shí)，
l = 0,r = 1,那么 mid = 0，邊界判定時(shí)要用 l <= mid && r <= right，否則就會(huì)跳過對(duì)比合并了
完整代碼如下
@Test
public void sortTest() {
int[] arr = new int[]{8, 4, 5, 7, 1, 3, 6, 2};
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
System.out.println("排序后：" + Arrays.toString(arr));
}
/**
* 分 和 合并
*/
public void mergeSort(int[] arr, int left, int right, int[] temp) {
//確保兩個(gè)數(shù)組中分別都存在至少一個(gè)數(shù)字
if (left < right) {
int mid = (left + right) / 2;
// 先分解左側(cè)
mergeSort(arr, left, mid, temp);
// 再分解右側(cè)
mergeSort(arr, mid + 1, right, temp);
// 最后合并
// 由于是遞歸，合并這里一定是棧頂?shù)南葓?zhí)行(兩邊數(shù)組各只有一個(gè)數(shù)時(shí))
// 第一次：left = 0,right=1
// 第二次：left = 2,right=3
// 第三次：left = 0，right=3
// System.out.println("left=" + left + "；right=" + right);
merge(arr, left, mid, right, temp);
}
}
/**
*
* 最難的是合并,所以可以先完成合并的方法，此方法請(qǐng)參考 基本思想 和 思路分析中的圖解來完成
* 動(dòng)腦筋
*
*
*
* @param arr 要排序的原始數(shù)組
* @param left 因?yàn)槭呛喜ⅲ砸玫阶笥覂蛇叺牡臄?shù)組信息，這個(gè)是左側(cè)數(shù)組的第一個(gè)索引值
* @param mid 因?yàn)槭且粋€(gè)數(shù)組，標(biāo)識(shí)是第一個(gè)數(shù)組的最后一個(gè)索引，即 mid+1 是右側(cè)數(shù)組的第一個(gè)索引，即中間索引
* @param right 右側(cè)數(shù)組的結(jié)束索引，右邊數(shù)組的最后一個(gè)數(shù)
* @param temp 臨時(shí)空間，臨時(shí)數(shù)組
*/
public void merge(int[] arr, int left, int mid, int right, int[] temp) {
// 定時(shí)臨時(shí)變量，用來遍歷數(shù)組比較
int l = left; // 左邊有序數(shù)組的初始索引
int r = mid + 1; // 右邊有序數(shù)組的初始索引
int t = 0; // temp 數(shù)組中當(dāng)前最后一個(gè)有效數(shù)據(jù)的索引
// 1. 按思路先將兩個(gè)數(shù)組（有序的）有序的合并到 temp 中
// 因?yàn)槭呛喜蓚€(gè)數(shù)組，所以需要兩邊的數(shù)組都還有值的時(shí)候才能進(jìn)行 比較合并
// 若其中一個(gè)數(shù)組的值遍歷完了（取完了），那么就跳出該循環(huán)，把另一個(gè)數(shù)組所剩的值，直接copy進(jìn)臨時(shí)數(shù)組即可
while (l <= mid && r <= right) {
// 如果左邊的比右邊的小，則將左邊的該元素填充到 temp 中
// 并移動(dòng) t++,l++,好繼續(xù)下一個(gè)
if (arr[l] < arr[r]) {
temp[t] = arr[l];
t++;//移動(dòng) temp 臨時(shí)數(shù)組中當(dāng)前最后一個(gè)有效數(shù)據(jù)的索引
l++; //左邊原始數(shù)組的索引移動(dòng)
}
// 否則則將右邊的移動(dòng)到 temp 中
else {
temp[t] = arr[r];
t++;//移動(dòng) temp 臨時(shí)數(shù)組中當(dāng)前最后一個(gè)有效數(shù)據(jù)的索引
r++;//右邊原始數(shù)組的索引移動(dòng)
}
}
// 2. 如果有任意一邊的數(shù)組還有值，則依序?qū)⑹Ｓ鄶?shù)據(jù)填充到 temp 中
// 如果左側(cè)還有值
while (l <= mid) {
temp[t] = arr[l];
t++;
l++;
}
// 如果右側(cè)還有值
while (r <= right) {
temp[t] = arr[r];
t++;
r++;
}
// 3. 將 temp 數(shù)組，拷貝到原始數(shù)組
// 注意：只拷貝當(dāng)前temp有效數(shù)據(jù)到對(duì)應(yīng)的原始數(shù)據(jù)中，通俗點(diǎn)說，就是原始數(shù)組中要排序的數(shù)據(jù)，通過temp排成了有序的，然后將temp中的有序數(shù)據(jù)將原始數(shù)組中原來要排序的那部分覆蓋了就行了
int tempL = left; // 從左邊開始拷貝，左邊第一個(gè)值的索引
t = 0; // temp 中的有效值索引，有效值邊界可以通過 right 判定，因?yàn)楹喜蓚€(gè)數(shù)組到 temp 中，邊界就是 right ，這里自己好好想想
/*
* 對(duì)于 8,4,5,7,1,3,6,2 這個(gè)數(shù)組,
* 從棧頂開始合并：8,4 | 5,7 1,3 | 6,2
* 先左遞歸的話：
* 第一次：8,4 合并：tempL=0，right=1
* 第二次：5,7 合并：tempL=2，right=3
* 第三次：4,8 | 5，7 進(jìn)行合并，tempL=0，right=3
* 直到左遞歸完成，得到左側(cè)一個(gè)有序的序列：4,5,7,8 然后再開始遞歸右邊那個(gè)無序的
* 最后回到棧底分解成兩個(gè)數(shù)組的地方，將兩個(gè)數(shù)組合并成一個(gè)有序數(shù)組
* 這里真的得自己想了，我只能這么說了。
*/
System.out.println("tempL=" + tempL + "; right=" + right);
while (tempL <= right) {
arr[tempL] = temp[t];
tempL++;
t++;
}
}
測(cè)試輸出
tempL=0; right=1
tempL=2; right=3
tempL=0; right=3
tempL=4; right=5
tempL=6; right=7
tempL=4; right=7
tempL=0; right=7
排序后：[1, 2, 3, 4, 5, 6, 7, 8]
從這里也可以看到，先左遞歸的話，可以看到最開始合并的索引是 0,1 也就是在棧頂開始首次遞歸時(shí)：兩個(gè)數(shù)組中分別只有一個(gè)數(shù)字。
最后一次合并：則是回到了最初棧底開始分解的方法，將兩個(gè)數(shù)組 0到7 進(jìn)行排序到臨時(shí)數(shù)組 temp ,最后將temp中的數(shù)據(jù)再?gòu)?code> 0到7 覆蓋到原始數(shù)組中。完成了排序 。
8 個(gè)數(shù)字，會(huì)進(jìn)行 7 次 合并
結(jié)合上面動(dòng)圖進(jìn)行思考。
對(duì)代碼的一些改進(jìn)
根據(jù)上述所講的基本思想和思路分析，對(duì)代碼進(jìn)行了一些改進(jìn)修改，減小代碼的臃腫。
public class MyMergeSortTest {
@Test
public void sortTest() {
int[] arr = new int[]{8, 4, 5, 7, 1, 3, 6, 2};
mergeSort(arr);
System.out.println("排序后：" + Arrays.toString(arr));
}
public void mergeSort(int arr[]) {
int[] temp = new int[arr.length];
doMergeSort(arr, 0, arr.length - 1, temp);
}
/**
* 分治 與 合并
*
* @param arr
* @param left
* @param right
* @param temp
*/
private void doMergeSort(int[] arr, int left, int right, int[] temp) {
// 當(dāng)還可以分解時(shí)，就做分解操作
if (left < right) {
int mid = (left + right) / 2;
// 先左遞歸分解
doMergeSort(arr, left, mid, temp);
// 再右遞歸分解
doMergeSort(arr, mid + 1, right, temp);
// 左遞歸分解到棧頂時(shí)，其實(shí)也是分為左右數(shù)組
// 左右都到棧頂時(shí)，開始合并：
// 第一次：合并的是 0,1 的索引,分解到最后的時(shí)候，其實(shí)只有一個(gè)數(shù)為一組，所以第一次合并是合并兩個(gè)數(shù)字
merge(arr, left, mid, right, temp);
}
}
/**
* 開始合并，每次合并都是兩組，第一次合并是兩個(gè)數(shù)字，左右一組都只有一個(gè)數(shù)字
*
* @param arr
* @param left
* @param mid
* @param right
* @param temp
*/
private void merge(int[] arr, int left, int mid, int right, int[] temp) {
// 1. 按照規(guī)則，將 temp 數(shù)組填充
// 2. 當(dāng)任意一邊填充完成后，剩余未填充的依次填充到 temp 數(shù)組中
// 3. 將 temp 數(shù)組的有效內(nèi)容，拷貝會(huì)原數(shù)組，也就是將這次排序好的數(shù)組覆蓋回原來排序的原數(shù)組中
int l = left; // 左側(cè)數(shù)組初始索引
int r = mid + 1; // 右側(cè)數(shù)組初始索引
int t = 0; // 當(dāng)前 temp 中有效數(shù)據(jù)的最后一個(gè)元素索引
// 1. 按照規(guī)則，將 temp 數(shù)組填充
// 當(dāng)兩邊都還有數(shù)字可比較的時(shí)候，進(jìn)行比較，然后填充 temp 數(shù)組
// 只要任意一邊沒有數(shù)值可用時(shí)，就僅需到下一步驟
while (l <= mid && r <= right) {
// 當(dāng)左邊比右邊小時(shí)，則填充到 temp 數(shù)組中
if (arr[l] < arr[r]) {
// 賦值完成后，t 和 l 都需要 +1，往后移動(dòng)一個(gè)位置
// t++ 是先把 t 進(jìn)行賦值，再進(jìn)行 t+1 操作
temp[t++] = arr[l++];
} else {
// 當(dāng)不滿足時(shí)，則說明 右側(cè)數(shù)字比左側(cè)的小，進(jìn)行右側(cè)的填充
temp[t++] = arr[r++];
}
}
// 2. 有可能有其中一邊會(huì)有剩余數(shù)字未填充到 temp 中，進(jìn)行收尾處理
while (l <= mid) {
temp[t++] = arr[l++];
}
while (r <= right) {
temp[t++] = arr[r++];
}
// 3. 將這個(gè)有序數(shù)組，覆蓋會(huì)原始排序的數(shù)組中
t = 0;
int tempL = left; // 從左側(cè)開始，到右側(cè)結(jié)束，就是這一次要合并的兩組數(shù)據(jù)
while (tempL <= right) {
arr[tempL++] = temp[t++];
}
}
}
大數(shù)據(jù)量耗時(shí)測(cè)試
/**
* 大量數(shù)據(jù)排序時(shí)間測(cè)試
*/
@Test
public void bulkDataSort() {
int max = 80000;
// max = 8;
int[] arr = new int[max];
for (int i = 0; i < max; i++) {
arr[i] = (int) (Math.random() * 80000);
}
if (arr.length < 10) {
System.out.println("原始數(shù)組：" + Arrays.toString(arr));
}
Instant startTime = Instant.now();
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
if (arr.length < 10) {
System.out.println("排序后：" + Arrays.toString(arr));
}
Instant endTime = Instant.now();
System.out.println("共耗時(shí)：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
}
多次測(cè)試輸出
共耗時(shí)：26 毫秒
共耗時(shí)：37 毫秒
共耗時(shí)：30 毫秒
共耗時(shí)：30 毫秒
復(fù)雜度
歸并排序比較占用內(nèi)存，但卻是一種效率高且穩(wěn)定的算法。
改進(jìn)歸并排序在歸并時(shí)先判斷前段序列的最大值與后段序列最小值的關(guān)系再確定是否進(jìn)行復(fù)制比較。如果前段序列的最大值小于等于后段序列最小值，則說明序列可以直接形成一段有序序列不需要再歸并，反之則需要。所以在序列本身有序的情況下時(shí)間復(fù)雜度可以降至O(n)。
TimSort可以說是歸并排序的終極優(yōu)化版本，主要思想就是檢測(cè)序列中的天然有序子段（若檢測(cè)到嚴(yán)格降序子段則翻轉(zhuǎn)序列為升序子段）。在最好情況下無論升序還是降序都可以使時(shí)間復(fù)雜度降至為O(n)，具有很強(qiáng)的自適應(yīng)性。
最好時(shí)間復(fù)雜度 最壞時(shí)間復(fù)雜度 平均時(shí)間復(fù)雜度 空間復(fù)雜度 穩(wěn)定性 傳統(tǒng)歸并排序 O(nlogn) O(nlogn) O(nlogn) T(n) 穩(wěn)定 改進(jìn)歸并排序 [1] O(n) O(nlogn) O(nlogn) T(n) 穩(wěn)定 TimSort O(n) O(nlogn) O(nlogn) T(n) 穩(wěn)定
我個(gè)人感覺歸并排序的邏輯相比快速排序來說更為容易理解，而且時(shí)間復(fù)雜度和快排一樣。關(guān)于快排的有關(guān)講解請(qǐng)看java 排序算法之快速排序。
到此這篇關(guān)于java 排序算法之歸并排序的文章就介紹到這了,更多相關(guān)java 歸并排序內(nèi)容請(qǐng)搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
原文鏈接：https://www.cnblogs.com/ljz111/p/15214257.html
