java如何實現歸并排序算法

# Java如何實現歸并排序算法

## 一、歸并排序概述

歸并排序（Merge Sort）是一種基于**分治法**（Divide and Conquer）的高效排序算法，由約翰·馮·諾伊曼在1945年首次提出。其核心思想是將原始數組遞歸地分成兩半，分別排序后再合并成一個有序數組。時間復雜度穩定為O(n log n)，是處理大規模數據時的優選算法之一。

### 算法特點
- **穩定性**：保持相等元素的原始順序
- **空間復雜度**：O(n)（需要額外存儲空間）
- **適用場景**：鏈表排序、外部排序（大數據文件）

## 二、算法實現步驟

### 1. 分解階段
將當前數組從中間位置分成左右兩個子數組，遞歸地對子數組進行分解，直到每個子數組只包含一個元素（天然有序）。

```java
void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // 防止整數溢出
        mergeSort(arr, left, mid);      // 遞歸左半部分
        mergeSort(arr, mid + 1, right); // 遞歸右半部分
        merge(arr, left, mid, right);  // 合并已排序的子數組
    }
}

2. 合并階段

將兩個已排序的子數組合并為一個有序數組：

void merge(int[] arr, int left, int mid, int right) {
    // 創建臨時數組
    int[] temp = new int[right - left + 1];
    
    int i = left;     // 左子數組起始索引
    int j = mid + 1;  // 右子數組起始索引
    int k = 0;        // 臨時數組索引
    
    // 比較兩個子數組元素
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    // 復制剩余元素
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    // 將臨時數組拷貝回原數組
    System.arraycopy(temp, 0, arr, left, temp.length);
}

三、完整Java實現

public class MergeSort {
    
    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        mergeSort(arr, 0, arr.length - 1);
    }
    
    private static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        
        while (i <= mid && j <= right) {
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        
        System.arraycopy(temp, 0, arr, left, temp.length);
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("排序前: " + Arrays.toString(arr));
        sort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

四、算法優化方案

1. 小數組切換插入排序

當子數組規模較小時（通常n < 15），插入排序的實際性能更好：

private static final int INSERTION_THRESHOLD = 7;

private static void mergeSort(int[] arr, int left, int right) {
    if (right - left <= INSERTION_THRESHOLD) {
        insertionSort(arr, left, right);
        return;
    }
    // ...原有邏輯
}

2. 避免重復分配臨時數組

在遞歸過程中復用同一個臨時數組：

public static void sort(int[] arr) {
    int[] temp = new int[arr.length];
    mergeSort(arr, 0, arr.length - 1, temp);
}

3. 提前終止判斷

如果左半部分最大值 <= 右半部分最小值，則無需合并：

if (arr[mid] <= arr[mid + 1]) return;

五、算法復雜度分析

六、與其他排序算法對比

七、實際應用場景

1. Java集合框架：Arrays.sort()對對象數組的排序采用TimSort（歸并排序的優化變種）
2. 外部排序：當數據量超過內存容量時，歸并排序是標準解決方案
3. 鏈表排序：歸并排序是鏈表排序的最佳選擇（只需O(1)額外空間）

八、常見問題解答

Q1: 為什么歸并排序需要額外空間？

因為合并過程需要臨時存儲兩個子數組的元素，無法在原數組上直接交換。

Q2: 如何實現自底向上的歸并排序？

使用迭代代替遞歸，從大小為1的子數組開始兩兩合并：

public static void bottomUpMergeSort(int[] arr) {
    int n = arr.length;
    int[] temp = new int[n];
    
    for (int size = 1; size < n; size *= 2) {
        for (int left = 0; left < n - size; left += 2 * size) {
            int mid = left + size - 1;
            int right = Math.min(left + 2 * size - 1, n - 1);
            merge(arr, left, mid, right, temp);
        }
    }
}

九、總結

歸并排序憑借其穩定的O(n log n)時間復雜度，成為處理大規模數據的重要工具。雖然需要額外空間，但其清晰的實現邏輯和優秀的穩定性使其在諸多場景下不可替代。理解歸并排序不僅有助于掌握分治思想，也為學習更復雜的算法（如外部排序、MapReduce等）奠定了基礎。 “`

文章共計約1650字，包含： 1. 算法原理說明 2. 分步驟代碼實現 3. 完整可運行示例 4. 多種優化方案 5. 復雜度分析 6. 實際應用場景 7. 常見問題解答 8. 格式化的對比表格 所有代碼均采用Java語法實現并附帶詳細注釋。