讨厌算法的程序员 | 第六章 归并排序

分而治之

从算法设计的分类上来说,插入排序属于增量方法。在排序好子数组A[1 ‥ j-1]后,再将单个元素A[j]插入子数组的适当位置,产生排序好的子数组A[1 ‥ j]。整个算法就是不断以此方法增量插入,直到子数组包含了所有数组元素。

本篇将要介绍的归并排序,是用另一种思想来解决排序问题的,在算法设计分类上属于分治法。

分治法思想是,将原问题分解为几个规模较小但类似于原问题的子问题,递归的求解这些子问题,然后在合并这些子问题的解,最终建立原问题的解。

这里提到一个词递归,其解释是:为了解决一个给定问题,算法一次或多次的调用其自身以解决紧密相关的子问题。递归是分治思想的一个具体实现。

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

1、分解:将原问题分解为若干子问题,这些子问题是原问题的规模较小的实例;

2、解决:递归的求解各子问题;

3、合并:合并子问题的解,得到原问题的解。

看到这里,“直觉”上可能会产生一个极大的疑问:最底层的子问题是在哪里解决的?产生这个疑问是正常的,因为第二步“解决”也仅仅是调用自身,其实就是重新进入了下一层的分解、解决和合并,而没有看到“如何解决”。

答案是:无需解决。换句话说,层层分解到子问题的规模足够小时,解就自己出现了。后面还会再提到这一点。

归并排序伪码

归并排序按照分治法的三个步骤如下:

  • 分解:分解待排序的n个元素的序列,变成各具n/2个元素的两个子序列;
  • 解决:递归的调用自身排序两个子序列;
  • 合并:合并两个已排序的子序列以产生最终排序的序列。

上一篇合并算法中已经解决了合并算法MERGE,归并排序就剩下如何进行分解,和递归调用了。

看代码的确就这三步:

MERGE-SORT(A, p, r) 1 if p < r 2 q = (p + r) / 2 3 MERGE-SORT(A, p, q) 4 MERGE-SORT(A, q+1, r) 5 MERGE(A, p, q, r)

注:(p + r) / 2如果不是整除,则取小于它的最大整数。

p < r时,表明数组有继续拆分的可能。当p ≥ r时,则表示该子数组最多有一个元素,所以无需排序就已经是排好序了,这就是分解到足够小会导致的自动解决。换句话说,我们一直把数组分解下去,直到分成每个子数组只包含1个元素时,即第3行中p = q,第4行中q+1 = r,那么第3和第4行的MERGE-SORT会立即返回,并执行MERGE,然后返回上一层MERGE-SORT,直到最上层。

一个例子

一个有8个元素的数组A[5, 2, 4, 7, 1, 3, 2, 6],采用归并排序的图示如下图。图中的下方蓝区部分是上面白区的数组不同时刻的镜像。

白区主要在做“分解”,蓝区主要在做“合并”。

归并排序

归并排序Java代码

public static void mergeSortInASC(int [] numbers, int p, int r) throws Exception {     if(p < r){        
 int q = (int)Math.floor((p + r) / 2);         
mergeSortInASC(numbers, p, q);         
mergeSortInASC(numbers, q + 1, r);         
mergeInASC(numbers, p, q, r);

   }
 }

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

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

递归算法复杂度Ω分析-分享

1. 深入认识递归 (1) 递归执行过程 例子:求N!。 这是一个简单的"累乘"问题,用递归算法也能解决。 n! ...

371
来自专栏desperate633

LeetCode 215. Kth Largest Element in an Array分析

显然最简单的思想就是排序,然后取出倒数第k个元素就可以了,我们可以直接调用内部的排序函数。

612
来自专栏大神带我来搬砖

如何编写更优雅的代码——java中用break语句模拟goto来中止代码块的执行

根据https://docs.oracle.com/javase/specs/jls/se7/html/jls-14.html, java的break语句不仅可...

2479
来自专栏TensorFlow从0到N

讨厌算法的程序员 3 - 算法分析基础

? 时间资源 上一篇,我们知道了如何用循环不变式来证明算法的正确性,本篇来看另一个重要方面:算法分析。分析算法的目的,是预测算法所需要的资源。资源不仅是指内存...

2483
来自专栏数据结构与算法

05:统计单词数

05:统计单词数 总时间限制: 1000ms 内存限制: 65536kB描述 一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位置,...

4487
来自专栏xiaoxi666的专栏

和为0的最长连续子数组【转载+优化代码】

题目描述和思路来自博客:http://www.cnblogs.com/coding-wtf/p/5849222.html,在此表示感谢。

382
来自专栏磐创AI技术团队的专栏

Tensorflow从入门到精通(二):附代码实战

1.Tensor介绍 Tensor(张量)是Tensorflow中最重要的数据结构,用来表示Tensorflow程序中的所有数据。Tensor本是广泛应用在物...

2827
来自专栏机器学习算法全栈工程师

实例介绍TensorFlow的输入流水线

在训练模型时,我们首先要处理的就是训练数据的加载与预处理的问题,这里称这个过程为输入流水线(input pipelines,或输入管道,[参考:https://...

1336
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第三章 算法分析基础

时间资源 上一篇,我们知道了如何用循环不变式来证明 算法的正确性,本篇来看另一个重要方面:算法分析。分析算法的目的,是预测算法所需要的资源。资源不仅是指内存、C...

2635
来自专栏TensorFlow从0到N

讨厌算法的程序员 6 - 归并排序

? 分而治之 分而治之 从算法设计的分类上来说,插入排序属于增量方法。在排序好子数组A[1 ‥ j-1]后,再将单个元素A[j]插入子数组的适当位置,产生排序...

2464

扫码关注云+社区