java歸并排序如何實現

Java歸并排序如何實現

歸并排序（Merge Sort）是一種基于分治法（Divide and Conquer）的經典排序算法。它的核心思想是將一個大的問題分解為多個小問題，分別解決這些小問題，最后將結果合并起來。歸并排序的時間復雜度為O(n log n)，是一種穩定的排序算法。本文將詳細介紹如何在Java中實現歸并排序。

歸并排序的基本思想

歸并排序的基本思想可以概括為以下三個步驟：

1. 分解：將待排序的數組遞歸地分解為兩個子數組，直到每個子數組只包含一個元素。
2. 排序：對每個子數組進行排序（由于子數組只包含一個元素，因此它們本身已經是有序的）。
3. 合并：將兩個有序的子數組合并為一個有序的數組。

Java實現歸并排序

下面是一個完整的Java實現歸并排序的代碼示例：

public class MergeSort {

    // 歸并排序的主方法
    public static void mergeSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        int[] temp = new int[array.length]; // 臨時數組用于存儲合并后的結果
        mergeSort(array, 0, array.length - 1, temp);
    }

    // 遞歸分解數組
    private static void mergeSort(int[] array, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + (right - left) / 2; // 計算中間位置
            mergeSort(array, left, mid, temp); // 對左半部分進行歸并排序
            mergeSort(array, mid + 1, right, temp); // 對右半部分進行歸并排序
            merge(array, left, mid, right, temp); // 合并兩個有序的子數組
        }
    }

    // 合并兩個有序的子數組
    private static void merge(int[] array, int left, int mid, int right, int[] temp) {
        int i = left; // 左半部分的起始索引
        int j = mid + 1; // 右半部分的起始索引
        int k = 0; // 臨時數組的起始索引

        // 將兩個子數組中的元素按順序合并到臨時數組中
        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        // 將左半部分剩余的元素復制到臨時數組中
        while (i <= mid) {
            temp[k++] = array[i++];
        }

        // 將右半部分剩余的元素復制到臨時數組中
        while (j <= right) {
            temp[k++] = array[j++];
        }

        // 將臨時數組中的元素復制回原數組
        k = 0;
        while (left <= right) {
            array[left++] = temp[k++];
        }
    }

    // 測試歸并排序
    public static void main(String[] args) {
        int[] array = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("排序前: " + Arrays.toString(array));
        mergeSort(array);
        System.out.println("排序后: " + Arrays.toString(array));
    }
}

代碼解析

1. mergeSort方法：這是歸并排序的入口方法。它首先檢查數組是否為空或只有一個元素，如果是，則直接返回。否則，創建一個臨時數組temp，并調用遞歸方法mergeSort進行排序。

2. 遞歸分解數組：mergeSort方法通過遞歸將數組分解為兩個子數組，直到每個子數組只包含一個元素。然后調用merge方法將兩個有序的子數組合并為一個有序的數組。

3. 合并兩個有序的子數組：merge方法負責將兩個有序的子數組合并為一個有序的數組。它使用三個指針i、j和k分別指向左半部分、右半部分和臨時數組的起始位置。通過比較兩個子數組中的元素，將較小的元素放入臨時數組中，直到其中一個子數組的所有元素都被合并。然后將剩余的元素復制到臨時數組中，最后將臨時數組中的元素復制回原數組。

4. 測試歸并排序：在main方法中，我們創建了一個測試數組，并調用mergeSort方法對其進行排序。排序前后分別打印數組的內容，以驗證排序的正確性。

總結

歸并排序是一種高效且穩定的排序算法，適用于大規模數據的排序。通過分治法，歸并排序將問題分解為多個小問題，分別解決后再合并結果。Java實現歸并排序的關鍵在于遞歸分解數組和合并兩個有序子數組。通過本文的代碼示例和解析，相信讀者已經掌握了如何在Java中實現歸并排序。