归并排序算法
- 归并排序原理:基于分治算法的排序方法,将问题分解为子问题,独立解决并合并结果。
- 分治策略实现:将数组分为两部分,分别排序后合并,重复此过程直到整个数组排序完成。
- 效率和应用:时间复杂度为 O(n*log n),适用于逆序数问题、外部排序和电子商务应用。
归并排序是基于分治算法原理的最流行的排序算法之一。
在这里,问题被分解为多个子问题。每个子问题都单独解决。最后,将子问题合并以形成最终解决方案。
分治策略
使用分治技术,我们将一个问题分解为子问题。当每个子问题的解决方案准备就绪时,我们会将子问题的结果'合并'起来以解决主问题。
假设我们需要对数组 A
进行排序。一个子问题将是对数组的一个子部分进行排序,从索引 p
开始,到索引 r
结束,表示为 A[p..r]
。
分解
如果 q
是位于 p
和 r
之间的中间点,那么我们可以将子数组 A[p..r]
分成两个数组 A[p..q]
和 A[q+1, r]
。
解决
在解决步骤中,我们尝试对子数组 A[p..q]
和 A[q+1, r]
进行排序。如果我们还没有达到基本情况,我们会再次分解这两个子数组并尝试对它们进行排序。
合并
当解决步骤达到基本步骤并且我们得到了两个已排序的子数组 A[p..q]
和 A[q+1, r]
用于数组 A[p..r]
时,我们通过创建一个已排序的数组 A[p..r]
来合并结果。
归并排序算法
MergeSort 函数重复地将数组分成两半,直到我们尝试在大小为1的子数组上执行 MergeSort,即 p == r
。
然后,合并函数开始工作,将已排序的数组合并成较大的数组,直到整个数组排序完成。
MergeSort(A, p, r):
if p > r
return
q = (p+r)/2
mergeSort(A, p, q)
mergeSort(A, q+1, r)
merge(A, p, q, r)
要对整个数组进行排序,我们需要调用 MergeSort(A, 0, length(A)-1)
。
如下图所示,归并排序算法递归地将数组分成两半,直到达到只包含1个元素的数组的基本情况。然后,合并函数将已排序的子数组取出并逐渐排序整个数组。
归并排序的合并步骤
每个递归算法都依赖于基本情况和组合基本情况结果的能力。归并排序也不例外。归并排序算法中最重要的部分是合并步骤。
合并步骤是解决将两个已排序列表(数组)合并以构建一个大已排序列表(数组)的简单问题。
该算法维护三个指针,一个用于两个数组中的每一个,另一个用于维护最终排序数组的当前索引。
已经到达了任一数组的末尾吗?
否:
比较两 个数组的当前元素
将较小的元素复制到已排序数组中
移动包含较小元素的元素的指针
是:
复制非空数组的所有剩余元素
编写合并算法的代码
我们上面描述的合并步骤和我们用于归并排序的合并步骤之间的一个显着差异是,我们仅对连续的子数组执行合并函数。
这就是为什么我们只需要数组、第一个位置、第一个子数组的最后索引(我们可以计算第二个子数组的第一个索引)和第二个子数组的最后索引。
我们的任务是合并两 个子数组 A[p..q]
和 A[q+1..r]
以创建一个已排序的数组 A[p..r]
。因此,函数的输入是 A、p、q 和 r。
合并函数的工作方式如下:
-
创建子数组的副本
L <- A[p..q]
和M <- A[q+1..r]
。 -
创建三个指针
i
、j
和k
。 -
i
维护L
的当前索引,从1开始。 -
j
维护M
的当前索引,从1开始。 -
k
维护A[p..q]
的当前索引,从p
开始。
直到 L
或 M
中的一个结束,选择 L
和 M
中元素中的较大者,并将它们放在 A[p..q]
的正确位置上。
当我们耗尽 L
或 M
中的元素时,将剩余元素拾起并放入 A[p..q]
。
在代码中,这将如下所示:
// 合并两个子数组 L 和 M 到 arr
void merge(int arr[], int p, int q, int r) {
// 创建 L ← A[p..q] 和 M ← A[q+1..r]
int n1 = q - p + 1;
int n2 = r - q;
int L[n1], M[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j
= 0; j < n2; j++)
M[j] = arr[q + 1 + j];
// 维护子数组和主数组的当前索引
int i, j, k;
i = 0;
j = 0;
k = p;
// 直到我们到达 L 或 M 的末尾之一,选择 L 和 M 中元素中较大的一个,并将它们放在 A[p..q] 的正确位置上
// 当我们耗尽 L 或 M 中的元素时,拾起剩余的元素并放入 A[p..q]
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = M[j];
j++;
k++;
}
}
逐步解释 Merge( ) 函数
这个函数里面发生了很多事情,让我们通过一个例子来看看它是如何工作的。
像往常一样,图片胜过千言万语。
数组 A[0..5]
包含两个已排序子数组 A[0..3]
和 A[4..5]
。让我们看看 merge 函数将如何合并这两个数组。
void merge(int arr[], int p, int q, int r) {
// 这里,p = 0, q = 4, r = 6(数组大小)
步骤 1:创建要排序的子数组的副本
// 创建 L ← A[p..q] 和 M ← A[q+1..r]
int n1 = q - p + 1 = 3 - 0 + 1 = 4;
int n2 = r - q = 5 - 3 = 2;
int L[4], M[2];
for (int i = 0; i < 4; i++)
L[i] = arr[p + i];
// L[0,1,2,3] = A[0,1,2,3] = [1,5,10,12]
for (int j = 0; j < 2; j++)
M[j] = arr[q + 1 + j];
// M[0,1] = A[4,5] = [6,9]
步骤 2:维护子数组和主数组的当前索引
int i, j, k;
i = 0;
j = 0;
k = p;
步骤 3:直到我们到达 L 或 M 的末尾之一,选择较大的元素并将它们放在 A[p..r] 的正确位置上
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i]; i++;
}
else {
arr[k] = M[j];
j++;
}
k++;
}