什麼是歸併排序？
合併排序是使用「分而治之」技術對資料進行排序的最常見演算法。在這個演算法中，問題被分成子問題，然後排序後將它們合併在一起。假設我們有一個未排序的數字列表，這是某個主題的班級結果。要按升序對它們進行排序，我們需要將它們放在從低到高開始的清單中。在此合併排序演算法中，列表將被分成更小的列表，以升序對它們進行排序，然後合併結果以便更好地理解。Java 中的歸併排序可以透過陣列 {6,9,8,2,4,1} 的範例來解釋，將其視為 10 類測試的結果。（結果的）陣列將被重複劃分分成更小的區塊，直到它們的大小為1。然後在對數字進行排序的同時進行合併過程。這將為我們提供從最低分到最高分的結果。
此數組將分為兩個數組，每個數組包含 3 個元素，如下面步驟 2中所示，並繼續劃分，直到在步驟 4中達到統一。然後，合併排序演算法開始一步一步地對數字進行排序（步驟 5 ），然後在步驟 6 和 7中將數字合併為一個更大的陣列。
執行
在實作中，我們將用 Java 編寫合併排序演算法的程式碼。所需的變數將是輸入數組和數組的長度。這兩個參數將進一步用於引入更多參數來建立合併排序函數。讓我們來看看下面的程式碼片段，了解 Java 中合併排序演算法的一般工作原理。Merge_Sort_Algo (Array, Beginning, End)
/** Three parameters required for the Merge Sort Algorithm
* Array = values of the array
* Beginning = the starting element of the array
* End = the ending element of the array*/
if (Beginning < End) // condition check Beginning must be less than End
set Middle = (Beginning + End) / 2 // Assigning Middle to the array
Merge_Sort_Algo (Array, Beginning, Middle) /** Sorting and merging of elements from Beginning to the Middle */
Merge_Sort_Algo (Array, Middle +1, End) /** Sorting and merging of elements from Middle to the End */
Merge (Array, Beginning, Middle, End) // Merging both the sorted arrays
end of if
End Merge_Sort_Algo例子
下面的Java程式碼解釋了合併排序演算法：import java.util.Arrays;
class HelloWorld {
public static void merge(
int[] array, int[] new_array_1, int[] new_array_2, int left, int right) {
// defining parameters
int i = 0, j = 0, k = 0;
while (i < left && j < right) { // conditions for merging
if (new_array_1[i] <= new_array_2[j]) {
array[k++] = new_array_1[i++];
}
else {
array[k++] = new_array_2[j++];
}
}
while (i < left) {
array[k++] = new_array_1[i++];
}
while (j < right) {
array[k++] = new_array_2[j++];
}
}
public static void mergeSort(int[] array, int length) { /** required parameters */
if (length < 2) { //condition for the length of array
return;
}
int middle = length / 2; // defining new parameter middle
int [ ] new_array_1 = new int [middle]; /** defining the new first array after division */
int [ ] new_array_2 = new int [length - middle]; /** defining the new second array */
for (int i = 0; i < middle; i++) { /**applying condition for sorting of new array 1 */
new_array_1 [ i ] = array [ i ];
}
for (int i = middle; i < length ; i++) { /**applying condition for sorting of new array 2 */
new_array_2 [ i - middle] = array [ i ];
}
mergeSort (new_array_1, middle); /** calling merge sort function for new array 1 */
mergeSort (new_array_2, length - middle); /** calling merge sort function for new array 2 */
merge(array, new_array_1, new_array_2, middle, length - middle); /** calling function for merging of new array 1 and new array 2 */
}
public static void main(String[] args) {
int [ ] testScores = {6,9,8,2,4,1};
int size = testScores.length;
System.out.println("Original Array " + Arrays.toString(testScores) + "\n");
mergeSort(testScores, size);
System.out.println("After Merge Sort " + Arrays.toString(testScores) + "\n");
}
}輸出
原始數組 [6, 9, 8, 2, 4, 1] 合併排序後 [1, 2, 4, 6, 8, 9]
結論
Java 中的歸併排序是一種從未排序的數字列表中獲取已排序列表的簡單演算法。應用「分而治之」的基本方法從未排序的陣列存取已排序的陣列。
GO TO FULL VERSION