算法基础——2、归并排序及算法设计

note

算法学习系列。一、算法基础——2、归并排序及算法设计

算法基础——1、插入排序及算法分析中,我们学会了插入排序算法,并了解到分析算法的方法。
这篇文章主要探讨如何设计算法。我们将具体讨论“分治法”的设计方法,使用分治法设计一个归并排序算法,并对分治法进行分析。

分治法

我们之前介绍的插入排序最坏情况运行时间为$\Theta(n^2)$,那么,我们有没有效率更高的排序方法呢?接下来我们将使用分治法来设计一个排序算法,以达到更高的效率。

递归与分治

首先,我们先了解一个概念——递归

  • 递归:即程序调用自身的编程技巧。

  • 为了解决一个较复杂的问题,算法多次递归地调用自身以解决若干相关的子问题,最后解决这个复杂的问题。

  • 许多高效的算法在结构上都是递归的。

我们给出一个生活中典型的递归例子——正整数的定义:

  • 1、$1$是正整数。

  • 2、如果$n$是正整数,那么$n+1$也是正整数。

  • 3、只有通过1、2定义出来的才是正整数。

上面的定义也是递归的:我们在还未完全定义正整数时就已经用到了这个概念,这和算法调用自身的性质是类似的。(是不是有点像数学归纳法呢?)

下面我们再给出一段计算阶乘的C++代码:

1
2
3
4
5
6
7
8
9
10
11
#include<cstdio>
using namespace std;
int f(int n){
return n==0? 1:f(n-1)*n;
}
int main(){
int a;
scanf("%d",&a);
printf("%d",f(a));
return 0;
}

很多递归算法实际上一般都是典型的分治法思想——将原问题分解成若干规模更小的子问题,继续递归求解子问题,最后合并这些子问题的解以得到原问题的解。

在阶乘计算中,我们就用到了这种思想,解释为数学语言即为:

$$f(n)=\begin{cases}1, & \text{n=0} \\ f(n-1) \times n, & \text{n≥1}\end{cases}$$

分治模式在每层递归时一般都有三个步骤:

  • 分解原问题为若干子问题,这些子问题都是原问题规模较小的情况。

  • 解决子问题,对子问题递归求解(继续分解子问题,规模足够小时则直接求解)。

  • 合并子问题的解以获得原问题的解。

归并排序

接下来我们将开始排序算法的设计,这种算法叫做归并排序,它区别于插入排序,完全遵循我们提到的分治模式:

  • 分解:将含有$n$个元素的序列分成两个各具$n/2$个元素的子序列。

  • 解决:使用归并排序递归(继续分解为$n/4,n/8…$)地排序这些子序列。

  • 合并:合并子序列,产生答案。

这样做,有一个关键的问题必须解决——如何合并子问题的解?

让我们再次回到扑克牌的例子:

现在桌上有两堆牌面朝上的牌,我们知道这两堆牌从上到下都已经从小到大排序,我们如何将这两堆牌合为一堆牌,并保证按顺序排列呢?

实际上很简单,我们每次选取露出的两张牌中的较小的一张,将它牌面朝下放置好,然后再比较新露出的牌,重复这个过程即可。

不难想到,我们合并的过程仅需要$\Theta(n)$的运行时间(我们最多执行$n$个基本操作)。

下面给出《算法导论》中的解决方案:

调用辅助过程$MERGE(A,p,q,r)$来完成合并

  • 其中,$A$是一个数组,$p,q,r$是数组下标,满足$p≤q<r$。

  • 该过程假设子数组$A[p..q]$和$A[q+1..r]$已排好序,它合并这两个子数组为已排好序的数组$A[p..r]$。

下面是这个过程的伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
MERGE(A,p,q,r)

n1=q-p+1
n2=r-q
let L[1..n1+1] and R[1..n2+1] be new arrays
for i=1 to n1
L[i]=A[p+i-1]
for j=1 to n2
R[j]=A[q+j]
L[n1+1]=∞
R[n2+1]=∞
i=1
j=1
for k=p to r
if L[i]≤r[j]
A[k]=L[i]
i=i+1
else A[k]=R[j]
j=j+1

大家可以尝试自行分析一下这个过程是怎样进行的。我们暂时不给出C++代码,最后再给出一个完整的程序。

现在我们可以将过程$MERGE$引入归并排序算法,下面的$MERGE-SORT(A,p,r)$将完成这个排序过程:

伪代码

1
2
3
4
5
6
7
MERGE-SORT(A,p,r)

if p<r
q=(p+r)/2 //ps:p+r为奇数则向下取整
MERGE-SORT(A,p,q)
MERGE-SORT(A,q+1,r)
MERGE(A,p,q,r)

这里给出完整的C++代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<cstdio>
#define max 999999999
using namespace std;
int a[200001],n;
void* merge(int* array,int p,int q,int r){
int n1=q-p+1;
int n2=r-q;
int L[100001],R[100001];
for(int i=1;i<=n1;i++){
L[i]=array[p+i-1];
}
for(int j=1;j<=n2;j++){
R[j]=array[q+j];
}
L[n1+1]=R[n2+1]=max;
int i=1;
int j=1;
for(int k=p;k<=r;k++){
if(L[i]<=R[j]){
array[k]=L[i];
i++;
}
else{
array[k]=R[j];
j++;
}
}
return 0;
}
void* merge_sort(int* array,int p,int r){
if(p<r){
int q=(p+r)/2;
merge_sort(array,p,q);
merge_sort(array,q+1,r);
merge(array,p,q,r);
}
return 0;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
merge_sort(a,1,n);
for(int j=1;j<=n;j++)
printf("%d ",a[j]);
return 0;
}

um…本人能力有限,代码写得有点丑,将就一下啦,大家可以尝试着自己写一写。。。

分析

我们就不再像上篇文章一样那么详细地去分析归并排序啦(好吧,我承认我懒,有空补上),我们这里直接给出结果:

过程$MERGE-SORT$的最坏情况运行时间

$$T(n)=\begin{cases}c, & \text{n=1} \\ 2T(n/2)+cn, & \text{n>1}\end{cases}$$

即$\Theta(n\times lg,n)$

最后更新于18-08-07
助力本站发展