Java 中的歸併排序程序

Java 中的歸併排序程式是使用最廣泛、最高效的演算法之一。合併排序基於分而治之技術，涉及將給定問題劃分為多個子問題並獨立解決每個子問題。當子問題解決後，我們將它們的結果結合起來得到問題的最終解決方案。合併排序演算法可以使用遞歸來實現，因為它涉及子問題而不是主要問題。

歸併排序是如何運作的？

讓我們考慮一個需要使用合併排序演算法進行排序的未排序數組。以下是將包含值 18、8、4、13、10、12、7 和 11 的陣列進行排序所涉及的步驟：

開始您的免費軟體開發課程

網頁開發、程式語言、軟體測試及其他

• 第一步涉及找到一個主元元素，在此基礎上我們的輸入數組將被劃分為子數組。
• 讓我們考慮選擇元素 13 作為主元；因此，原始數組將被分成兩個子數組。第一個子數組將包含 18, 8, 4, 13，第二個子數組將包含其餘元素 10, 12, 7, 11。
• 將步驟 2 中獲得的子數組依照步驟 1 進一步細分，如此繼續。
• 一旦主數組被劃分為具有單一元素的子數組，我們就開始再次合併這些子數組，以使合併後的元素按排序順序排列。
• 以下是實際分而治之的工作原理：

Java 中的歸併排序程式

下面是一個程式碼範例，展示了 java 中合併排序的實作：

代碼：

package com.edubca.sorting;
public class MergeSort {
private int[] array;
private int[] tempMergedArr;
private int length;
public static void main(String a[]){
int[] inputArr = {18, 8, 4, 13, 10, 12, 7, 11};
MergeSort mergeSort = new MergeSort();
mergeSort.sort(inputArr);
for(int i:inputArr){
System.out.print(i + " ");
}
}
public void sort(int inputArr[]) {
this.array = inputArr;
this.length = inputArr.length;
this.tempMergedArr = new int[length];
performMergeSort(0, length - 1);
}
private void performMergeSort(int lowerIndex, int higherIndex) {
if (lowerIndex < higherIndex) {
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
// Sort the left side of the array call performMergeSort recursively
performMergeSort(lowerIndex, middle);
// Sort the right side of the array call performMergeSort recursively
performMergeSort(middle + 1, higherIndex);
// Merge subparts using a temporary array
mergeData(lowerIndex, middle, higherIndex);
}
}
private void mergeData (int lowerIndex, int middle, int higherIndex) {
for (int i = lowerIndex; i <= higherIndex; i++) {
tempMergedArr[i] = array[i];
}
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) {
if (tempMergedArr[i] <= tempMergedArr[j]) {
array[k] = tempMergedArr[i];
i++;
} else {
array[k] = tempMergedArr[j];
j++;
}
k++;
}
while (i <= middle) {
array[k] = tempMergedArr[i];
k++;
i++;
}
}
}

上面的程式碼將產生一個排序數組作為輸出。

輸出：

我們什麼時候應該使用歸併排序？

歸併排序可以用在以下場景：

• 當要排序的資料結構不支援隨機存取時，合併排序會很有幫助且有效率。
• 當需要高水準的並行性時，可以使用歸併排序，因為可以使用並行運行的多個進程獨立解決不同的子問題。
• 使用鍊錶時合併排序速度較快，因為在合併清單時可以輕鬆變更指標。
• 合併排序可以被認為是一種穩定排序，這意味著陣列中的相同元素保持其相對於彼此的原始位置。如果需要高穩定性，可以採用歸併排序。  

歸併排序的複雜度分析

以下幾點分析歸併排序的複雜度：

• 歸併排序是一種遞歸演算法，在所有三種情況（最差、最佳和平均）下，其時間複雜度均為O(n*log n)，因為歸併排序將數組分成相等的兩半，並花費線性時間來合併它們.
• 歸併排序的空間複雜度為 O(n)，因為它採用遞歸方法。因此，合併排序可以被認為是一種快速、空間和時間高效的演算法。

合併排序與其他演算法的比較

以下幾點將合併排序與其他演算法進行比較：

• 堆排序與歸併排序有相同的時間複雜度，但它只需要 O(1) 輔助空間，而不是歸併排序的 O(n)。因此，堆排序比合併排序更節省空間。
• 對於基於 RAM 的陣列進行排序，快速排序實作通常優於合併排序。
• 在使用鍊錶時，合併排序優於快速排序和堆排序演算法，因為指標可以輕鬆更改。

結論-Java 中的歸併排序程式

文章的結論是，合併排序是演算法中需要理解的重要概念。

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