您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 歸併排序算法詳解與分治法實現

編輯：Java 相關知識

算法思想：分治法

分解：將數組二分遞歸，直到單元素（天然有序）。
解決：合併兩個有序子數組為一個有序數組。
合併：雙指針線性掃描，輔助臨時數組。

核心合併邏輯

private static void merge(int[] data, int left, int mid, int right) {
    int[] tmp = new int[data.length];
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        tmp[k++] = (data[i] <= data[j]) ? data[i++] : data[j++];
    }
    while (i <= mid) tmp[k++] = data[i++];
    while (j <= right) tmp[k++] = data[j++];
    // 複製回原數組
    System.arraycopy(tmp, left, data, left, right - left + 1);
}

完整遞歸實現

public static void mergeSort(int[] data) {
    sort(data, 0, data.length - 1);
}
private static void sort(int[] data, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) >>> 1;
    sort(data, left, mid);
    sort(data, mid + 1, right);
    merge(data, left, mid, right);
}

複雜度與特性

優化方向

小數組閾值（如 ≤ 45）切換插入排序，減少遞歸開銷。
合併前檢查 data[mid] <= data[mid+1]，已有序則跳過合併。
自底向上迭代版本避免遞歸棧溢出。
鏈表結構可實現 O(1) 空間合併（僅調整指針）。

測試運行

public static void main(String[] args) {
    int[] data = {38, 27, 43, 3, 9, 82, 10};
    System.out.println("原始: " + Arrays.toString(data));
    mergeSort(data);
    System.out.println("有序: " + Arrays.toString(data));
}
// 輸出: [3, 9, 10, 27, 38, 43, 82]