🔀 合併排序法完整教學
程式碼、原理與運作演示
← 回到排序法選單
📌 基本概念
合併排序法（Merge Sort） 是一種有效率的分治法排序演算法。其基本思想是：將序列不斷對半分割，直到每個子序列只剩一個元素，再將這些子序列兩兩合併成有序序列，最終合併成完整的排序結果。
合併排序法的時間複雜度為 O(n log n)，無論最佳、最壞或平均情況皆如此，且屬於穩定排序。缺點是需要額外的記憶體空間。
⚙️ 操作原理與動畫演示
輸入數列，點擊「開始排序動畫」即可觀察合併排序的每一步。
開始排序動畫
（可自訂數列，逗號分隔）
⚙️ 詳細運作原理
演算法步驟：
1
分割： 將序列從中間分成兩半。
2
遞迴排序： 對左右兩半分別遞迴進行合併排序。
3
合併： 將兩個已排序的子序列合併成一個有序序列。
虛擬程式碼：
function mergeSort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = mergeSort(arr[:mid])
right = mergeSort(arr[mid:])
return merge(left, right)
function merge(left, right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
result += left or right
return result
📊 具體例子 - 排序 [5, 2, 8, 1, 9]
初始陣列： [5, 2, 8, 1, 9]
分割為 [5, 2] 和 [8, 1, 9]
[5, 2] → 分割為 [5]、[2] → 合併為 [2, 5]
[8, 1, 9] → 分割為 [8]、[1, 9] → [1, 9] 分割為 [1]、[9] → 合併為 [1, 9] → [8] 與 [1, 9] 合併為 [1, 8, 9]
最後 [2, 5] 與 [1, 8, 9] 合併為 [1, 2, 5, 8, 9]
💻 C語言完整程式碼
#include <stdio.h>
// 合併兩個子陣列
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// 合併排序主函數
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
int numbers[] = {5, 2, 8, 1, 9};
int n = sizeof(numbers)/sizeof(numbers[0]);
printf("原始數列: ");
for (int i = 0; i < n; i++) {
printf("%d ", numbers[i]);
}
printf("\n\n");
mergeSort(numbers, 0, n-1);
printf("排序後的數列: ");
for (int i = 0; i < n; i++) {
printf("%d ", numbers[i]);
}
printf("\n");
return 0;
}
⏳ 時間與空間複雜度
最佳/平均/最壞時間複雜度 O(n log n) 空間複雜度 O(n) 排序穩定性 穩定
優點：
適合大量資料排序，效率高
排序結果穩定
時間複雜度穩定
缺點：
← 回到排序法選單