萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Java 遞歸歸併排序算法完整實現與過程可視化

歸併排序採用**分治法**:遞歸將數組拆分為單元素,再合併兩個有序數組。時間複雜度穩定 O(n log n),空間複雜度 O(n)。

歸併排序分治過程圖解

完整 Java 實現 (含過程打印)

import java.util.Arrays;

public class MergeSortTest {

    public static void main(String[] args) {
        int[] arr = {10, 9, 12, 4, 11, 7, 8, 3};
        System.out.println("原始: " + Arrays.toString(arr));
        sort(arr);
        System.out.println("最終: " + Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        int[] tmp = new int[arr.length]; // 輔助數組,避免重複分配
        mergeSort(arr, tmp, 0, arr.length - 1);
    }

    // 遞歸分治入口
    private static void mergeSort(int[] arr, int[] tmp, int left, int right) {
        if (left < right) {
            int mid = (left + right) >>> 1; // 無符號右移防溢出
            mergeSort(arr, tmp, left, mid);      // 左半遞歸
            mergeSort(arr, tmp, mid + 1, right); // 右半遞歸
            merge(arr, tmp, left, mid, right);   // 合併
            System.out.println("合併後 [" + left + "-" + right + "]: " + Arrays.toString(arr));
        }
    }

    // 合併兩個有序區間 [left, mid] 和 [mid+1, right]
    private static void merge(int[] arr, int[] tmp, int left, int mid, int right) {
        int i = left;      // 左區間指針
        int j = mid + 1;   // 右區間指針
        int k = left;      // tmp 寫入指針

        // 雙指針歸併
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
            else tmp[k++] = arr[j++];
        }
        // 複製剩餘元素
        while (i <= mid) tmp[k++] = arr[i++];
        while (j <= right) tmp[k++] = arr[j++];

        // 寫回原數組
        System.arraycopy(tmp, left, arr, left, right - left + 1);
    }
}

運行輸出過程可視化

原始: [10, 9, 12, 4, 11, 7, 8, 3]
合併後 [0-1]: [9, 10, 12, 4, 11, 7, 8, 3]
合併後 [2-3]: [9, 10, 4, 12, 11, 7, 8, 3]
合併後 [0-3]: [4, 9, 10, 12, 11, 7, 8, 3]
合併後 [4-5]: [4, 9, 10, 12, 7, 11, 8, 3]
合併後 [6-7]: [4, 9, 10, 12, 7, 11, 3, 8]
合併後 [4-7]: [4, 9, 10, 12, 3, 7, 8, 11]
合併後 [0-7]: [3, 4, 7, 8, 9, 10, 11, 12]
最終: [3, 4, 7, 8, 9, 10, 11, 12]

關鍵點解析

  1. 輔助數組 tmp 在頂層分配一次,遞歸傳遞複用,避免 O(n log n) 空間浪費。
  2. 雙指針合併 為核心邏輯,利用哨兵或邊界判斷簡化代碼。
  3. System.arraycopy 批量拷貝 比手寫循環快 (JVM 內部優化)。
  4. 穩定性: arr[i] <= arr[j] 保證相等元素相對順序不變。
  5. 迭代版 (自底向上): 避免遞歸棧溢出,大數組首選。

複雜度與對比

算法平均時間最差時間空間穩定
歸併排序O(n log n)O(n log n)O(n)✅
快速排序O(n log n)O(n²)O(log n)❌
堆排序O(n log n)O(n log n)O(1)❌
TimSort (Java/JDK)O(n log n)O(n log n)O(n)✅

Java Arrays.sort() 對象數組用 TimSort (歸併+插入優化),基本類型用雙軸快排。理解歸併排序是掌握分治思想、外部排序、倒序數統計的基石。

copyright © 萬盛學電腦網 all rights reserved