🌟個人博客：www.hellocode.top
🏰Java知識導航：Java-Navigate
🔥CSDN：HelloCode.
🌞知乎：HelloCode
🌴掘金：HelloCode
?如有問題，歡迎指正，一起學習~~

---

當談到高效的排序算法時，歸并排序是一個備受推崇的選擇。歸并排序是一種分治算法，它將一個大問題分解成若干個小問題，然后逐個解決這些小問題，并將它們合并成一個整體的解。

基本思想

這里采用五分鐘學算法大佬的圖解，十分清晰

1. 分解階段： 將待排序數組分成兩個相等或近似相等的子數組，不斷將問題規模縮小。
2. 解決階段： 遞歸地對兩個子數組進行排序，直到子數組的長度為1（即已有序）。
3. 合并階段： 將排好序的子數組合并成一個有序的數組，這是歸并排序的核心操作。

三個階段，涉及到遞歸就比較難理解（個人感覺），最好配合動畫好好理解理解。主要就是分解和歸并（將大問題分解為小問題，再通過歸并過程合并并排序）

代碼實現

每次隨便寫數組挺麻煩的，后續就都使用我寫的工具類來生成隨機數組了~

歸并排序相對難理解一些，主要涉及到分解和歸并，將待排序數組一個個拆分，直到拆分為1個1組（無需排序），接下來就是自底向上逐個合并，在合并的同時進行排序操作，最終合并好的就是有序的數組了

/*** @author HelloCode* @blog https://www.hellocode.top* @date 2023年08月15日 19:33*/
public class MergeSort {public static void main(String[] args) {// 生成容量為15的由100以內隨機數構成的int數組(用到了自己寫的一個工具類)int[] arr = ArrayUtil.randomIntArray(15, 100);System.out.println("原數組：" + Arrays.toString(arr));mergeSort(arr);System.out.println("排序后：" + Arrays.toString(arr));}private static void mergeSort(int[] arr) {if (arr == null || arr.length <= 1) {return; // 數組為空或只有一個元素，無需排序}// 創建臨時數組（避免多次創建）int[] temp = new int[arr.length];// 遞歸入口sort(arr, temp, 0, arr.length - 1);}// 拆分private static void sort(int[] arr, int[] temp, int left, int right) {// 遞歸出口if (left >= right) {return;}// 記錄中間值（左邊數組的末尾，+1為右邊數組的起始）int mid = left + ((right - left) >> 1);// 開始拆分sort(arr, temp, left, mid);sort(arr, temp, mid + 1, right);// 歸并merge(arr, temp, left, mid, right);}// 歸并（排序）private static void merge(int[] arr, int[] temp, int left, int mid, int right) {// 記錄臨時數組索引int p = left;// 左半邊起始索引int i = left;// 右半邊起始索引int j = mid + 1;// 開始歸并// 兩邊都還有的情況while(i <= mid && j <= right){if(arr[i] <= arr[j]){temp[p++] = arr[i++];}else{temp[p++] = arr[j++];}}// 左邊還有剩余的情況（直接加到臨時數組末尾）while(i <= mid){temp[p++] = arr[i++];}// 右邊還有剩余的情況（直接加到臨時數組末尾）while(j <= right){temp[p++] = arr[j++];}// 將臨時數組拷貝回原數組for(int k = left; k <= right; k++){arr[k] = temp[k];}}
}

測試：

原數組：[83, 49, 19, 75, 26, 64, 59, 60, 11, 97, 36, 41, 17, 31, 69]
排序后：[11, 17, 19, 26, 31, 36, 41, 49, 59, 60, 64, 69, 75, 83, 97]

生成隨機數組的工具類：

/*** @author HelloCode* @blog https://www.hellocode.top* @date 2023年08月13日 20:01*/
public class ArrayUtil {private static final Random RANDOM = new Random();public static int[] randomIntArray(int capacity,int max){// 創建capacity大小的數組（1~max）int[] res = new int[capacity];for(int i = 0; i < capacity; i++){res[i] = RANDOM.nextInt(max) + 1;}return res;}
}

優化

歸并排序本身是一個穩定且效率較高的排序算法，但還是有一些優化方法可以進一步提升性能：

1. 插入排序優化： 對于小規模子數組，使用插入排序可以提高性能。當子數組長度小于一定閾值時，切換到插入排序可以減少遞歸調用開銷。
2. 自底向上歸并： 在歸并階段，可以使用自底向上的方法，避免遞歸調用，從而減少棧空間的使用。
3. 優化合并操作： 在合并階段，如果左子數組的最大元素小于右子數組的最小元素，可以直接跳過合并操作，因為兩個子數組已經有序。

總結

優點

1. 歸并排序穩定且適用于各種數據類型。
2. 具有穩定的時間復雜度O(n log n)，適用于大規模數據排序。
3. 分治思想使其易于理解和實現，同時也為優化提供了空間。

缺點

1. 歸并排序需要額外的存儲空間來存儲臨時數組，空間復雜度較高。
2. 在小規模數據排序時，性能稍遜于快速排序。

復雜度

• 時間復雜度：平均情況、最好情況和最壞情況下的時間復雜度均為O(n log n)。
• 空間復雜度：空間復雜度為O(n)，需要額外的存儲空間來存儲臨時數組。

使用場景

• 歸并排序適用于需要穩定排序的場景，對性能有一定要求。
• 特別適合用于外部排序，如在磁盤上對大文件進行排序。

通過分治思想，歸并排序將排序問題分解為小問題，并通過合并操作將它們逐步解決，從而實現高效且穩定的排序。這使得歸并排序成為計算機科學中重要的算法之一。