歸併排序演算法

深入了解歸併排序演算法

歸併排序演算法的核心思想是分治法，即「分而治之」。它將一個數組遞歸地劃分為更小的子數組，直到每個子數組只包含一個元素（此時已排序）。然後，它將這些子數組合併成更大的已排序數組。值得注意的是，排序過程發生在合併階段，而不是在分割階段。

演算法示範

假設我們有一個待排序的陣列：

我們將陣列分成左右兩個子數組：

繼續遞歸分割，直到每個子數組都只有一個元素：

接下來，合併並排序這些子陣列：較小的值放在左邊，較大的值放在右邊。

最終完成排序：

程式碼實作 (Java)

最初的Java程式碼存在一些效率問題，我們可以對其進行最佳化。改進後的程式碼如下：

import java.util.Arrays;

public static void mergeSort(int[] array) {
    int n = array.length;
    if (n < 2) {
        return;
    }
    int middle = n / 2;
    int[] left = Arrays.copyOfRange(array, 0, middle);
    int[] right = Arrays.copyOfRange(array, middle, n);

    mergeSort(left);
    mergeSort(right);

    int leftIndex = 0;
    int rightIndex = 0;
    int arrayIndex = 0;

    while (leftIndex < left.length || rightIndex < right.length) {
        if (leftIndex < left.length && (rightIndex >= right.length || left[leftIndex] <= right[rightIndex])) {
            array[arrayIndex++] = left[leftIndex++];
        } else {
            array[arrayIndex++] = right[rightIndex++];
        }
    }
}

這段最佳化後的程式碼使用了Arrays.copyOfRange()方法來更有效率地複製數組元素，並簡化了合併過程中的循環條件和判斷語句，從而提高了程式碼的可讀性和效率。

希望這段改進後的解釋和程式碼能幫助你更好地理解歸併排序演算法！

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