合併排序
合併排序是最流行、最高效的排序演算法之一。它是基於分治演算法的原理。它的工作原理是將陣列反覆分成兩半，直到我們將陣列分成單個元素。單元素本身就是一個排序的陣列。合併排序將這些小的排序陣列反覆合併，產生更大的排序子陣列，直到我們得到一個最終的排序陣列。它被廣泛應用於電子商務應用中。
合併排序演算法
自上而下的合併排序方法從全陣列的頂部開始，向下遞迴到單個元素。
假設我們有一個未排序的陣列 A[]，包含 n 元素。
MergeSort()
-
取兩個變數
beg&end，然後儲存起始元素和結束元素的索引。 -
利用公式
mid =(beg+end)/2找到陣列的中間點，將陣列分成兩半。 -
將陣列分成兩部分
arr[beg, .... , mid]和arr[mid+1, .... , end]。 -
利用遞迴將陣列反覆劃分成單元素的子陣列。
-
呼叫 merge 函式開始構建排序陣列。
Merge()
-
初始化輔助陣列
output來儲存排序後的輸出。 -
初始化 3 個指標
i、j和k。i指向第一個子陣列beg的開始。
j指向第二個子陣列mid+1的開始。
k用beg初始化，保持排序陣列output的當前索引。 -
直到到達
arr[beg, .... ,mid]或arr[mid+1, .... ,end]子陣列的末尾，我們在索引i&j的元素中挑出一個較小的值，插入到output中。 -
當其中一個陣列用完後，挑選剩餘的元素插入
output中。 -
將
output複製到arr[beg, ... , end]中。
合併排序示例
假設我們有陣列：(5,3,4,2,1,6)。我們將使用合併排序演算法對其進行排序。
| 操作 | (5,3,4,2,1,6) |
mergesort(0,5) |
|---|---|---|
divide |
(5,3,4) (2,1,6) |
mergesort(0,2) mergesort(3,5) |
divide |
(5,3) (4) (2,1) (6) |
mergesort(0,1) mergesort(2,2) mergesort(3,4) mergesort(5,5) |
divide |
(5) (3) (4) (2) (1) (6) |
陣列分解為單個元素 |
merge |
(3,5) (4) (1,2) (6) |
merge(0,1) merge(2,2) merge(3,4) merge(5,5) |
merge |
(3,4,5) (1,2,6) |
merge(0,2) merge(3,5) |
merge |
(1,2,3,4,5,6) |
merge(0,5) |
我們得到排序的陣列 - (1 2 3 4 5 6)。
合併排序演算法的實現
#include<iostream>
using namespace std;
void merge(int arr[], int beg, int mid, int end) {
int output[end - beg + 1];
int i = beg, j = mid + 1, k = 0;
// add smaller of both elements to the output
while (i <= mid && j <= end) {
if (arr[i] <= arr[j]) {
output[k] = arr[i];
k += 1; i += 1;
}
else {
output[k] = arr[j];
k += 1; j += 1;
}
}
// remaining elements from first array
while (i <= mid) {
output[k] = arr[i];
k += 1; i += 1;
}
// remaining elements from the second array
while (j <= end) {
output[k] = arr[j];
k += 1; j += 1;
}
// copy output to the original array
for (i = beg; i <= end; i += 1) {
arr[i] = output[i - beg];
}
}
void mergeSort(int arr[], int beg, int end) {
if (beg < end) {
int mid = (beg + end) / 2;
//divide and conquer
mergeSort(arr, beg, mid); // divide : first half
mergeSort(arr, mid + 1, end); // divide: second half
merge(arr, beg, mid, end); // conquer
}
}
int main() {
int n = 6;
int arr[6] = {5, 3, 4, 2, 1, 6};
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
mergeSort(arr, 0, n - 1); // Sort elements in ascending order
cout << "Output array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
合併排序演算法的複雜度
時間複雜度
- 平均情況
合併排序是一種遞迴演算法。下面的遞迴關係給出了合併排序的時間複雜度表示式。
T(n) = 2T(n/2) + θ(n)
這個遞迴關係的結果給出了 T(n)=nLogn.我們也可以把它看作是一個大小為 n 的陣列被分成最多的 Logn 部分，每一部分的合併需要 O(n) 時間。
因此，時間複雜度是 [Big Theta]：O(nLogn)。
- 最壞情況
最壞情況下的時間複雜度為[大 O]：O(nLogn)。
- 最佳情況
最佳情況下的時間複雜度是 [Big Omega]：O(nLogn)。它與最壞情況下的時間複雜度相同。
空間複雜度
合併排序演算法的空間複雜度為 O(n)，因為在輔助陣列中儲存排序子陣列需要 n 個輔助空間。
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn