總目錄：地址如下看總綱
1圣勒、并歸排序介紹
歸并排序（MERGE-SORT）是利用歸并的思想實(shí)現(xiàn)的排序方法衣摩，該算法采用經(jīng)典的分治（divide-and-conquer）策略
（分治法將問(wèn)題分(divide)成一些小的問(wèn)題然后遞歸求解惩激，
而治(conquer)的階段則將分的階段得到的各答案"修補(bǔ)"在一起咙轩，即分而治之)。
2屿聋、基本思想
image.png
說(shuō)明:
1空扎、可以看到這種結(jié)構(gòu)很像一棵完全二叉樹(shù)，本文的歸并排序我們采用遞歸去實(shí)現(xiàn)（也可采用迭代的方式去實(shí)現(xiàn)）润讥。
2转锈、分階段可以理解為就是遞歸拆分子序列的過(guò)程
3、思路拆解圖
再來(lái)看看治階段楚殿，我們需要將兩個(gè)已經(jīng)有序的子序列合并成一個(gè)有序序列撮慨，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個(gè)已經(jīng)有序的子序列脆粥，合并為最終序列[1,2,3,4,5,6,7,8]
image.png
4砌溺、代碼
/**
* title:
* @author 阿K
* 2020年12月15日 下午10:55:51
*/
public class MergeSort {
public static void main(String[] args) {
// int arr[] = { 8, 4, 5, 7, 1, 3, 6, 2 };
// 創(chuàng)建要給80000個(gè)的隨機(jī)的數(shù)組
int[] arr = new int[8000000];
for (int i = 0; i < 8000000; i++) {
arr[i] = (int) (Math.random() * 8000000); // 生成一個(gè)[0, 8000000) 數(shù)
}
new QuickSort(arr);
//new MergeSort(arr);
}
public MergeSort(int[] arr) {
int temp[] = new int[arr.length]; // 歸并排序需要一個(gè)額外空間
long time = new Date().getTime();
mergeSort(arr, 0, arr.length - 1, temp);
long time2 = new Date().getTime();
System.out.println("并歸排序 排" + (arr.length) + "個(gè)數(shù)據(jù)，使用" + (time2 - time) + "毫秒");
}
// 并歸(分+治)排序 Api
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2;// 中間索引
// 向左遞歸分解
mergeSort(arr, left, mid, temp);
// 向右遞歸分解
mergeSort(arr, mid + 1, right, temp);
// 合并
merge(arr, left, mid, right, temp);
}
}
/**
* 合并的方法
*
* @param arr 排序的原始數(shù)組
* @param left 左邊有序序列的初始索引
* @param mid 中間索引
* @param right 右邊索引
* @param temp 做中轉(zhuǎn)的數(shù)組
*/
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left; // 初始化 i,左邊有序序列的初始索引
int j = mid + 1;// 初始化 j,右邊有序序列的初始索引
int t = 0; // 指向 temp 數(shù)組的當(dāng)前索引
// (一)
// 1变隔、先把左右兩邊（有序）的數(shù)據(jù)规伐，按照規(guī)則填充到 temp數(shù)組
// 2、直到左右兩邊有序序列匣缘，有一邊處理完畢為止
while (i <= mid && j <= right) {// 執(zhí)行條件
// 若左邊有序序列的當(dāng)前元素猖闪，小于等于右邊有序序列的當(dāng)前元素
// 則將左邊的當(dāng)前元素鲜棠，填充到 temp 數(shù)組
// 之后再 t++, i++
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
t += 1;
i += 1;
} else {// 反之，將右邊有序序列的當(dāng)前元素填充到 temp 數(shù)組中
temp[t] = arr[j];
t += 1;
j += 1;
}
}
// (二)把有剩下數(shù)據(jù)的一邊的數(shù)據(jù)培慌，依次全部填充到temp 中
while (i <= mid) {
// (1) 左邊有序序列的剩余所有元素豁陆，填充到 temp
temp[t] = arr[i];
t += 1;
i += 1;
}
while (j <= right) {
// (2) 右邊有序序列的剩余所有元素，填充到 temp
temp[t] = arr[j];
t += 1;
j += 1;
}
// (三)
// 將 temp 數(shù)組拷貝到 arr
// 注： 并非每次都拷貝所有
t = 0;
int tempLeft = left;
// 第一次合并 tempLeft = 0 , right = 1 // tempLeft = 2 right = 3 // tL=0 ri=3
// 最后一次 tempLeft = 0 right = 7
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}
}
5吵护、性能測(cè)試---800W個(gè)數(shù)據(jù)( 并歸 VS 快排)
image.png
image.png
得幾乎差不讀盒音。
