使用Java實現歸併排序算法

歸併排序的Java實現¶

什麼是歸併排序？¶

歸併排序（Merge Sort）是一種基於分治思想的高效排序算法。它的核心思路是將一個大問題分解爲多個小問題，解決小問題後再合併結果。具體來說，就是先將數組分成兩半，遞歸地對每一半進行排序，最後將兩個有序的子數組合併成一個完整的有序數組。

歸併排序的核心步驟¶

歸併排序遵循“分而治之”的思想，分爲三個步驟：
1. 分解（Divide）：將待排序數組從中間分成左右兩個子數組，直到每個子數組只有一個元素（此時自然有序）。
2. 解決（Conquer）：遞歸地對左右兩個子數組進行排序。
3. 合併（Combine）：將兩個有序的子數組合併成一個更大的有序數組。

用Java實現歸併排序¶

下面通過一個具體的例子來理解如何用Java實現歸併排序。我們使用一個簡單的整數數組作爲示例，逐步講解代碼邏輯。

1. 遞歸排序方法（mergeSort）¶

首先，我們需要一個遞歸方法來實現分解和解決步驟。方法的核心邏輯是：
- 如果數組長度小於等於1，直接返回（已經是有序的）。
- 計算數組中間位置，遞歸排序左右兩個子數組。
- 合併兩個有序子數組。

public class MergeSort {
    // 歸併排序主方法
    public static void mergeSort(int[] arr) {
        // 遞歸終止條件：數組長度小於等於1時，無需排序
        if (arr.length <= 1) {
            return;
        }
        // 計算中間索引，將數組分成左右兩部分
        int mid = arr.length / 2;
        // 遞歸排序左半部分
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        mergeSort(left);
        // 遞歸排序右半部分
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        mergeSort(right);
        // 合併左右兩個有序子數組
        merge(arr, left, right);
    }
}

2. 合併方法（merge）¶

合併是歸併排序的關鍵步驟，需要將兩個有序子數組合併爲一個有序數組。具體邏輯：
- 使用三個指針分別遍歷左子數組、右子數組和合並後的結果數組。
- 比較左右子數組的元素，將較小的元素放入結果數組。
- 將剩餘未遍歷完的元素直接複製到結果數組。

import java.util.Arrays;

public class MergeSort {
    // ... 省略mergeSort方法 ...

    // 合併兩個有序子數組到原數組arr
    private static void merge(int[] result, int[] left, int[] right) {
        int i = 0; // 左子數組指針
        int j = 0; // 右子數組指針
        int k = 0; // 結果數組指針
        // 比較左右子數組元素，將較小值放入結果數組
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k] = left[i];
                i++;
            } else {
                result[k] = right[j];
                j++;
            }
            k++;
        }
        // 將左子數組剩餘元素複製到結果數組
        while (i < left.length) {
            result[k] = left[i];
            i++;
            k++;
        }
        // 將右子數組剩餘元素複製到結果數組
        while (j < right.length) {
            result[k] = right[j];
            j++;
            k++;
        }
    }
}

3. 完整代碼與測試¶

將上述方法整合，編寫一個完整的Java程序並測試：

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 3, 7, 6, 1, 8};
        System.out.println("排序前：" + Arrays.toString(arr));
        mergeSort(arr);
        System.out.println("排序後：" + Arrays.toString(arr));
    }

    // 歸併排序主方法
    public static void mergeSort(int[] arr) {
        if (arr.length <= 1) {
            return;
        }
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        mergeSort(left);
        mergeSort(right);
        merge(arr, left, right);
    }

    // 合併兩個有序子數組
    private static void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k] = left[i];
                i++;
            } else {
                result[k] = right[j];
                j++;
            }
            k++;
        }
        while (i < left.length) {
            result[k] = left[i];
            i++;
            k++;
        }
        while (j < right.length) {
            result[k] = right[j];
            j++;
            k++;
        }
    }
}

運行結果：

排序前：[5, 2, 9, 3, 7, 6, 1, 8]
排序後：[1, 2, 3, 5, 6, 7, 8, 9]

算法分析¶

時間複雜度：
每次合併需要遍歷整個數組（O(n)），遞歸深度爲 log n（將數組分解爲兩半的次數），因此總時間複雜度爲 O(n log n)。
空間複雜度：
需要額外的臨時數組（長度爲 n）存儲合併結果，空間複雜度爲 O(n)。
穩定性：
歸併排序是穩定排序（相等元素的相對順序不會改變），因爲合併時若兩元素相等，會優先取左子數組的元素放入結果數組。

總結¶

歸併排序通過“分而治之”的思想實現高效排序，時間複雜度爲 O(n log n)，適合處理大數據量的排序場景。雖然需要額外空間，但邏輯清晰且易於理解，是初學者學習分治算法的經典案例。通過遞歸分解和合並有序子數組，最終得到完整的有序數組。