了解歸併排序演算法（附Java範例）

合併排序：綜合指引

合併排序是一種高效的排序演算法，經常在各種程式語言中使用，無論是獨立的還是作為混合方法的一部分。 它的基礎在於分而治之的典範：一個問題被分解成更小的子問題，單獨解決，然後將它們的解決方案組合起來得到最終結果。 合併排序遞歸地將輸入清單分成兩半，對每一半進行排序，然後合併已排序的兩半以產生完全排序的清單。

理解合併排序過程

讓我們使用範例陣列來說明合併排序過程：

此圖描繪了陣列的遞歸劃分。

此圖顯示了排序子陣列的合併。

實現合併排序

以下是歸併排序演算法的 Java 實作：

import java.util.Arrays;

public class MergeSortTest {
    public static void main(String[] args){
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length-1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    static void mergeSort(int arr[], int start, int end){
        if (start < end){
            int mid = (start + end) / 2;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid + 1, end);
            merge(arr, start, mid, end);
        }
    }

    static void merge(int arr[], int start, int mid, int end){
        int[] left = new int[(mid - start) + 1];
        int[] right = new int[end - mid];

        for(int i = 0; i <= mid - start; i++)
            left[i] = arr[start + i];
        for(int j = 0; j < end - mid; j++)
            right[j] = arr[mid + 1 + j];

        int i = 0, j = 0;
        int k = start;

        while (i < left.length && j < right.length){
            if(left[i] <= right[j]){
                arr[k] = left[i];
                i++;
            }
            else{
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while (i < left.length){
            arr[k] = left[i];
            i++;
            k++;
        }

        while (j < right.length){
            arr[k] = right[j];
            j++;
            k++;
        }
    }
}

代碼說明

mergeSort 方法遞歸地分割數組，直到子數組只包含一個元素。 merge 方法至關重要；它會取得已排序的子陣列並將它們有效地合併為單一已排序的陣列。 合併過程涉及比較兩個子數組中的元素並將較小的元素放入主數組中。

此圖說明了合併步驟。

程式碼的輸出是：

未排序數組：[8,2,6,4,9,1] 排序數組：[1, 2, 4, 6, 8, 9]

演算法複雜度

• 時間複雜度： 在所有情況下（最佳、平均和最差）O(n log n)。這是因為無論輸入數組的初始順序如何，分而治之的方法都保持一致。
• 空間複雜度： O(n)，因為合併作業期間臨時陣列需要額外的空間。

以上是了解歸併排序演算法（附Java範例）的詳細內容。更多資訊請關注PHP中文網其他相關文章！