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

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

归并排序的英文叫做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

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

原文：http://www.cnblogs.com/yunyao/p/3826249.html