讨厌算法的程序员 | 第五章 合并算法

本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。

之所以把它独立成一篇,一方面是一旦了解了它再理解归并排序就会简单很多,另一方面是其本身就具有独立性,可以解决很多常见问题,并不非得寄宿在归并排序里面。

合并算法,就是将两个已经各自排好序的序列,合并成一个排好序的大序列的方法。

经典应用

两摞扑克牌

《算法导论》里面给出的例子就很好理解。还是拿扑克牌来说事:桌上有两摞牌,面朝上,每摞都已经按照从小到大排好序了。那么如何把它们合并成一摞并排好序呢?

日常生活中其实还有很多类似的应用。比如校园里学生按身高由低到高排队,偶尔会遇到两队合一队的情况,要求合并后仍然按照由低到高的顺序。

合并算法就是解决此类问题的最佳方法。以扑克牌为例,其基本步骤是:

1 、比较两堆牌最顶上的两张牌,选最小的一张;

2 、将其拿出来(此时该堆顶上将露出一张新牌),面朝下放到输出堆(就是最终的那一大摞);

3 、重复上面两步,直到原来两堆其中一个为空,此时将另一堆中的所有剩余的牌,直接面朝下放到输出堆中。

假设最坏情况是两摞牌要比到各自最后一张,此时算法时间复杂度是T(n) = Θ(n),这是因为整个算法最多只要遍历一遍。

伪码

接下来,用伪码实现上面的思想,但有两个额外的变化:

1、扑克应用中的两摞牌已经排好序换一种表达方式:A是一个数组,p、q和r是数组下标,满足p≤q<r,假设A[p ‥ q]和A[q+1 ‥ r]都已排好序。期望的输出是:A的子数组A[p ‥ r]是通过合并原A[p ‥ q]和A[q+1 ‥ r]形成的且已排好序的子数组。

2、为了避免每次执行基本步骤都要检查是否有堆为空,在每个堆的底部放置一张“哨兵”牌(哨兵通常包含一个特殊值,用于简化代码),值为∞。它可以保证直到两堆牌都露出∞时,其他牌都已经放置到输出堆。因为我们事先知道刚好r - p + 1张牌将被放置到输出堆,所以一旦已执行r - p + 1个基本步骤,算法就可以停止了。

定义算法的名字为MERGE,伪码如下:

MERGE(A, p, q, r)
1  n1 = q - p + 1
2  n2 = r - q
3  let L[1 ‥ n1+1] and R[1 ‥ n2+1] be new arrays
 4  for i = 1 to n1
5    L[i] = A[p+i-1]
6  for j = 1 to n2
7    R[j] = A[q+j]
8  L[n1+1] = ∞
9  R[n2+1] = ∞
10 i = 1
11 j = 1
12 for k = p to r
13   if L[i] ≤ R[j]
14     A[k] = L[i]
15     i = i + 1
16   else A[k] = R[j]
17     j = j + 1

正确性证明

证明算法的正确性中提到:只要证明在初始、保持、和终止阶段循环不变式都成立,从而可以通过终止时的不变式推断出算法是正确的。

代码中的12~17行是唯一的循环,循环不变式是什么呢?这里我们令输出A[p ‥ k-1]作为循环不变式,迭代的任何过程中随k的增加该数组总是按从小到大的顺序包含原A[p ‥ r]中最小的元素,有如下证明:

  • 初始化:循环第一次迭代之前,k = p,所以子数组A[p ‥ k-1]为空;
  • 保持:即要证明某次迭代之前不变式为真,下次迭代之前不变式仍为真;
    • 假设某次迭代前,L[i] ≤ R[j],此时L[i]是未被复制回数组A的最小元素;
    • 与此同时,数组A[p ‥ k-1]包含k - p个最小元素,即迭代前不变式为真;
    • 第14行代码将L[i]复制到A[k]之后,子数组A[p ‥ k]将包含k - p + 1个最小元素。增加k的值(for循环)和i的值(第15行代码)后,即为下次迭代前重新建立了该循环不变式;
    • 反之,若L[i] > R[j],则第16~17代码执行适当的操作来维持该循环不变式。
  • 终止:终止时k = r + 1。子数组A[p ‥ k-1]就是A[p ‥ r]且按从小到大的顺序包含了L[1 ‥ n1+1]和R[1 ‥ n2+1]中的k - p = r - p + 1个最小元素。数组L和R一共包含n1 + n2 + 2 = r - p + 3个元素,多出的2个就是哨兵,其他所有元素都已经被复制回数组A。

时间复杂度

前面提到过MERGE的时间复杂度是Θ(n),其中n = r - p + 1。再快速算下:

  • 代码13行和811行中的每行需要常量时间;
  • 代码4~7行的for循环需要Θ(n1+n2) = Θ(n)的时间;
  • 代码12~17行for循环有n次迭代,每次迭代需要常量时间。

JAVA实现

public class MergeSort {
public static void mergeInASC(int[] numbers, int p, int q, int r) throws Exception {   if(numbers.length < 2 || p > q || q >= r)         
throw new Exception("Para error.");      

int n1 = q - p + 1;    
int n2 = r - q;     

 int[] L = new int[n1 + 1];    
 int[] R = new int[n2 + 1];      
for(int i  = 0; i < n1; i++){         
L[i] = numbers[p + i];     
}     
for(int j = 0; j < n2; j++){         
R[j] = numbers[q + 1 + j];    
 }     
 L[n1] = Integer.MAX_VALUE;     
R[n2] = Integer.MAX_VALUE;      
int i = 0;    
 int j = 0;    
 for(int k = p; k <= r; k++){        
 if(L[i] > R[j]){            
 numbers[k] = R[j];            
 j++;        
 }        
 else{             
numbers[k] = L[i];            
 i++;        
 }     
}
 }
 }

MergeSort.java下载(https://github.com/EthanYuan/algorithm/tree/master/src/algorithm)

原文发布于微信公众号 - 人工智能LeadAI(atleadai)

原文发表时间:2017-09-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏TensorFlow从0到N

讨厌算法的程序员 5 - 合并算法

本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。 之所以把它独立成一篇,一方面是一旦...

3215
来自专栏猿人谷

查找链表中倒数第k个结点

题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。链表结点定义如下: struct ListNode { in...

1895
来自专栏前端杂货铺

汉字数组排序及如何检测汉字

起因         最近接触了一道有意思的题目,就是单击表格的表头,根据表头的那一栏进行排序。恰好有一栏的数据全部是中文汉字,如果仅仅对于汉字数组使用默认的s...

2683
来自专栏函数式编程语言及工具

泛函编程(2)-初次体验泛函编程

    泛函编程和数学方程式解题相似;用某种方式找出问题的答案。泛函编程通用的方式包括了模式匹配(pattern matching)以及递归思维(Recursi...

1869
来自专栏简书专栏

Python面对对象编程

面向过程:根据业务逻辑从上到下写代码 函数式:将某功能代码封装到函数中,日后便无需重复填写,仅调用函数即可 面对对象:对函数进行分类和封装,让开发"更好更快...

643
来自专栏小樱的经验随笔

【Java学习笔记之三十一】详解Java8 lambda表达式

Java 8 发布日期是2014年3月18日,这次开创性的发布在Java社区引发了不少讨论,并让大家感到激动。特性之一便是随同发布的lambda表达式,它将允许...

3065
来自专栏C语言及其他语言

【编程经验】关于链表、还有编译器

关注我们 最近有小白来问VC6.0和其他编译器怎么下,小编回了一些,但是也是确实比较多......所以今天就不单单分享知识了,还要分享资源! ...

27910
来自专栏TungHsu

这或许是对小白最友好的python入门了吧——18,定义函数

有的时候我们写的代码往往是一个功能组合,并且这组代码可能会很复杂,但是我们在写代码的时候可能会多次用到这组代码,每次都写这么多代码浪费时间并且检查、修改起来也很...

3247
来自专栏听Allen瞎扯淡

由 Java 到 Scala:如何优雅的跳出循环

在开发过程中,我们经常会遇到这样的需求:循环执行某个操作,当满足一定条件的时候循环终止。最常见的场景就是累加数组中的元素,一直到大于某个值,用伪代码来描述就是:

491
来自专栏程序猿DD

你真的了解lambda吗?一文让你明白lambda用法与源码分析

本文链接: http://www.cmlanche.com/2018/07/22/lambda用法与源码分析/

552

扫描关注云+社区