排序算法系列——归并排序

记录学习点滴,菜鸟成长记

归并排序的英文叫做Merge-Sort,要想明白归并排序算法,还要从“递归”的概念谈起。

1.递归

一般来讲,人在做决策行事的时候是往往是从已知出发,比如,我又要举个不恰当的例子了→_→:

  • 看到漂亮姑娘→喜欢人家→追→女朋友→老婆

但是人家施瓦辛格不是这么想的,人家从小就立志当总统:

  • 要当总统←先当州长←竞选州长要有钱←那得找个有钱妹子←妹子都喜欢明星←身材好能当明星←健身

递归,就像一个人对自己的发展有清晰的规划和坚定的信心一样,他知道每一步会有怎么样的结果,他需要仅仅是一颗救命稻草,一旦抓住,最终结果是抱住参天大树。

 1 def f(n):#求一个数的阶乘
 2     if n==1:
 3         return 1
 4     else:
 5         return n*f(n-1)
 6 def F(willbe):#求我如何成为天下第一
 7     if willbe == canbe:
 8         return ‘be this‘
 9     else:
10         return willbe + F(willbe.needbe)
  • 类比于经典的递归应用,求一个数的阶乘,我写了一个求我如何成为天下第一。
  • 递归,我的理解就是前世因缘已经注定,要做的就是快速找到前世的因,也就是程序里的终止条件。

最后,我想说的是,要理解递归,你先要理解递归。这个出自:要理解递归,你需要先理解递归……

2.分治模式:

分治模式就不谈了,一般的分治法就是老生常谈的:分解、解决、合并

3.归并

下面我们来解释什么是归并,首先我们还是从那副扑克牌说起,你觉得一个人给扑克牌排序没啥意思,这时你叫上了一个朋友,将扑克牌分成两堆,约定各自排各自的,两人都排好自己的顺序后在合并,不一会你两就排好了。

怎么合并呢?其实很简单,你们把两摞扑克牌放在桌面上,开始比较每一摞最上面的牌,哪张牌最小你就拿起哪张,后拿起的牌放在先前拿起的牌的后面,不一会你两就将这副牌排好顺序了。

然后你觉得这个游戏很有意思,你又叫来了2个人,然后大家一起愉快的排扑克牌了;你觉得还是不够尽兴,于是又叫了50个人,这时每个人手里都有一张牌,由于人太多,不得不并了两张桌子来让大家坐下(假设一张桌子能做27个人,没看过哈利波特吗,XD...)。。。恩,大家还是把所有牌放在桌子上,由于人太多,你就安排了1个桌长,你两各负责一张桌子;你和小组长觉得还是管不过来,于是你两又各自在自己负责区域分了两个小组长,分下去的小组长也很懒,他们准备继续行使自己的权力,就这样分啊分,一共分了54个小组长,大家你看你,我看我。。。

不管了,你只负责你分的两个小组长,最后你和你认命的桌长一起完成此次艰巨的任务。

  • 写到这里的时候,我想起我当时看过的《三体》,脑海中浮起的是大刘给我们描述的三体人组成的计算机

4.实现

归并排序的关键是归并两个排好序的数组,按照《导论》使用Python实现如下

 1 def Merge(A,p,q,r):
 2     L = A[p-1:q+1-1]#p表示实际的下标,写完算法再-1
 3     R = A[q+1-1:r+1-1]
 4     temp = []
 5     while len(L) > 0 and len(R) > 0:
 6         if L[0] > R[0]:
 7             temp.append(R.pop(0))
 8         else:
 9             temp.append(L.pop(0))
10     if len(L) > 0:
11         temp.extend(L)
12     if len(R) > 0:
13         temp.extend(R)
14     A[p-1:r+1-1] = temp
15 def MergeSort(A,p,r):
16     if p<r:
17         q = (p+r)/2
18         MergeSort(A,p,q)
19         MergeSort(A,q+1,r)
20         Merge(A,p,q,r)
  • 这里必须吐槽一下:我是在Eclipse中用PyDev写的Python程序,尽然没有变量检测,由于输入中有个r,新建R最初写的是r,尽然没有报错,Debug了一下午才发现,看来还是心不静,曾记得看过一句话,说得十分在理,天下程序,唯慢不破。

5.更新

排序算法系列——归并排序,布布扣,bubuko.com

时间: 07-04

排序算法系列——归并排序的相关文章

排序算法系列——堆排序

记录学习点滴,菜鸟成长记 堆排序引入了另一种算法设计技巧:使用一种我们称之为“堆”的数据结构来进行数据管理. 堆排序算是真正意义上的利用数据结构来求解数组排序的方法. “插入排序”和“归并排序”可以看做是一种“计算机体力活”,体现的思想更多的是去模拟最简单的人类思维,比如插入排序过程中的比较,归并中子问题合并时的比较. “堆排序”可以看做是“计算机脑力活”,他利用了一种结构化的语言来表达,这种结构化带来一些性质,比如左右孩子.比[堆大小的一半向下取整]大的下标都是叶节点不需要维护其最大堆性质等.

算法系列——归并排序

归并排序基本思路就是将数组分成二组A,B,如果这二组组内的数据都是有序的,那么就可以很方便的将这二组数据进行排序.如何让这二组组内数据有序了? 可以将A,B组各自再分成二组.依次类推,当分出来的小组只有一个数据时,可以认为这个小组组内已经达到了有序,然后再合并相邻的二个小组就可以了.这样通过先递归的分解数列,再合并数列就完成了归并排序. #include <iostream> #include <string> #include <algorithm> #include

常用排序算法之——归并排序

归并排序的原理: 如果数组的元素个数大于1,则: 将数组平均分为两部分: 左边的数组归并排序:递归 右边的数组归并排序:递归 将两个各自有序的数组合并,需要一个额外的辅助数组,暂时保存合并结果:返回 否则,数组元素个数为1时,已经有序:直接返回. 稳定排序.时间复杂度在最坏.最好.平均情况下都为O(N lgN),空间复杂度为O(N). 代码: 1 #include <iostream> 2 using namespace std; 3 4 template<typename T>

排序算法系列——快速排序

记录学习点滴 快速排序算法是一种很有趣的算法,短小精悍,性能强劲,对于大部分情况都可以胜任,但对极端环境难以应付. 快速排序我理解为:这是一个“以自我为中心的”+“分治法”思想的算法. 分治法不必多说,化繁为简,那就是逐个击破. 那什么是“以自我为中心”?顾名思义,就是每次都一个“我”,每个人都要围绕“我”行事,比“我”小的都去左边站着,比“我”他大的都去右边站着,而且“我”不去关心每一边都有谁,反正你没“我”大或者小就行.一旦“我”落位了妥帖了,“我”就不动了.然后再在左右两边分别产生新“我”

排序算法系列——八大排序算法对比分析

本系列最后一篇,综合分析下前面介绍的八种排序算法的效率,以及各自的适用情况. 下面先看看八种排序算法的时间复杂度表格: 图中八种排序被分成了两组,一组时间复杂度为O(n^2),另一组相对高效些. 下面先对第一组O(n^2)的四种排序算法进行对比,分别取数组长度为100,1000,10000,100000四个数量级,各个元素在0-10000000之间随机获取.下面看下结果的分析. 排序算法 长度=100 长度=1000 长度=10000 长度=100000 直接插入排序 535 2,198 135

我的Java开发学习之旅------&amp;gt;Java经典排序算法之归并排序

一.归并排序 归并排序是建立在归并操作上的一种有效的排序算法,该算法是採用分治法(Divide and Conquer)的一个很典型的应用.将已有序的子序列合并,得到全然有序的序列.即先使每一个子序列有序.再使子序列段间有序.若将两个有序表合并成一个有序表.称为二路归并. 归并过程为:比較a[i]和a[j]的大小.若a[i]≤a[j],则将第一个有序表中的元素a[i]拷贝到r[k]中,并令i和k分别加上1.否则将第二个有序表中的元素a[j]拷贝到r[k]中,并令j和k分别加上1.如此循环下去.直

排序算法之归并排序(Mergesort)解析

一.归并排序的优缺点(pros and cons) 耗费心思来理解它,总要有个理由吧: 归并排序的效率达到了巅峰:时间复杂度为O(nlogn),这是基于比较的排序算法所能达到的最高境界 归并排序是一种稳定的算法(即在排序过程中大小相同的元素能够保持排序前的顺序,3212升序排序结果是1223,排序前后两个2的顺序不变),这一点在某些场景下至关重要 归并排序是最常用的外部排序方法(当待排序的记录放在外存上,内存装不下全部数据时,归并排序仍然适用,当然归并排序同样适用于内部排序...) 缺点: 归并

选择排序 —— 排序算法系列

假设我们有如下一个数组: 使用选择排序算法对这个数组进行排序,步骤如下: 第 1 次 在下标0到6之间找到最小的数字,我们可以发现最小的数字是15,它在下标为4的位置上: 把下标4上面的数字跟下标0上面的数字互换,得到排序如下图的数组: 第 2 次 在下标1到6之间找到最小的数字,我们可以发现最小的数字是33,它在下标为5的位置上: 把下标5上面的数字跟下标1上面的数字互换,得到排序如下图的数组: 第 3 次 在下标2到6之间找到最小的数字,我们可以发现最小的数字是48,它在下标为5的位置上:

排序算法系列——直接选择排序

前面两篇介绍了两种插入排序算法:直接插入排序和希尔排序.这篇介绍选择排序的一种:直接选择排序.从名字就可以看出直接选择排序与直接插入排序很相似,两者相同点在与都是将待排序序列分成有序区和无序区两部分,不同之处在于直接插入排序是从无序区选出一个插入到有序区合适的位置,而直接选择排序是从无序区选出最小的一个插入到有序区尾部,使得有序区保持有序. 基本思想: 一组待排序的数据,首先将其划分成两部分,一部分是已排好序的,另一部分是待排序的,然后依次从待排序部分取出最小的元素插入到已排序部分的尾部,保证有