合并排序
合并排序是最流行、最高效的排序算法之一。它是基于分治算法的原理。它的工作原理是将数组反复分成两半，直到我们将数组分成单个元素。单元素本身就是一个排序的数组。合并排序将这些小的排序数组反复合并，产生更大的排序子数组，直到我们得到一个最终的排序数组。它被广泛应用于电子商务应用中。
合并排序算法
自上而下的合并排序方法从全数组的顶部开始，向下递归到单个元素。
假设我们有一个未排序的数组 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