大家好，你们期待的第二版终于发布了！如果你还没有看过第一版，那么我就把这个链接送给你。

前言

如果您已经看完了第一版，那么，第二版就可以开始看喽。不过，第二版十分的难，我会尽量讲解清楚，把他们简化，希望读者对这些排序有一些了解。
今天要讲解的算法是：

• 归并排序
• 快速排序
• 堆排序
• 树的搜索：广度优先和深度优先（只讲原理，没有代码，科普一下😐）。

这些的确很难不过我会把它尽量简化。大家请认真看。由于要讲解堆排序，希望您对堆有一些了解。至于堆嘛，本人很懒，没有单独写😁。那就请大家自行查找数据结构：堆。如果您非想要听我讲堆……那么，评论区或者私聊告诉我就行了。还有，归并排序和快速排序都要用到递归，也请大家自行搜索：递归

本文字数多，大家请认真看，或者后慢慢看。

废话不多说了，开始讲解喽！

堆排序

堆排序简介：传送门

这个看的不太顺眼，不过习惯就好哦😝。

大家先看完这个动图，然后我来分析一下。
首先，把数组里面的的元素全部取出来，构建一个的堆。
然后，从大到小取出。
因此，可以总结出两步：

构堆，取顶。

这是我自己总结的，构堆，就是构建堆，取顶，就是一个一个，从顶部取出取出。
看到这里，也许您在想该怎么弄一个堆呢？答案是，我们不用弄一个堆！为什么呢？我们用数组表示一个堆。如图：

堆的图片来源于网络，下面的数组是自己写的

发现，BC是A的子节点，DE是B的子节点，FG是D的……
发现子节点是父节点的下标加……好像没有规律啊。
没事，列个表就知道了

这就是一道简单的小学找规律题，先自己想一下……

这里给一个小例子：

 def SonItoFaI(sonindex): #函数名太怪了，意思是Sonindextofatherindex 😜         sonindex = sonindex/2 if sonindex==int(sonindex): #整数减一 return sonindex-1 else: return int(sonindex) 

知道了这些，**重点来了**！

重点

构堆

我们该怎么构建一个堆呢，或者是说把数组变成堆的样子呢？很简单，从1开始迭代。每一个都求出它的父节点的下标（前面已经有函数了）如果他比父节点要大，就交换，一直交换到他到最顶上（下标为0）或者它比父节点要小，才停止。

def buildHeap(arr): for x in range(1,len(arr)): #从1开始是因为下标为0的他没有父节点了！ while True: pass 

先判断x是否为0，是的话跳出，然后判断是否大于父节点，大于继续比较，否则跳出。

def buidHeap(arr): for x in range(1,len(arr)): while True:             f = SonItoFaI(x) #父节点 if x == 0: break if arr[x]>arr[f]:                 arr[x],arr[f],x = arr[f],arr[x],f             else: break return arr  

这就可以构建一个堆了，感觉是否很简单？不过代码也挺长的。

取顶

这里，请大家先了解一下arr[xxx:xxx]的用法，如果不会，那么，送你一个礼物：收下吧！
看一眼就回来吧。
如果你认真的看过堆的资料，那么您一定知道对取出最上面的顶点应该由最下面的代替上去，然后重新构造堆。那么最下面的，不也就是最后面的？直接和最后面的交换就行了！当然，这里的最后面的，指的是已经排序好的那一堆，的前面。

def takeout(arr): for x in range(1,len(arr)): pass 

然后交换，重新构造堆：

def takeout(arr): for x in range(1,len(arr)):         arr[0],arr[len(arr)-x] = arr[len(arr)-x],arr[0]         a=buidHeap(arr[0:len(arr)-x-1]) 

最后：

def takeout(arr): for x in range(1,len(arr)):         arr[0],arr[len(arr)-x] = arr[len(arr)-x],arr[0]         a=buidHeap(arr[0:len(arr)-x-1])         arr[0:len(arr)-x-1] = a     return arr 

封装

把这三个函数封装成函数（直接复制，没有注释，请谅解）：

def heapsort(arr): def SonItoFaI(sonindex):          sonindex = sonindex/2 if sonindex==int(sonindex): return sonindex-1 else: return int(sonindex) def buidHeap(arr): for x in range(1,len(arr)): while True:                 f = SonItoFaI(x) if x == 0: break if arr[x]>arr[f]:                     arr[x],arr[f],x = arr[f],arr[x],f                  else: break return arr     def takeout(arr): for x in range(1,len(arr)):             arr[0],arr[len(arr)-x] = arr[len(arr)-x],arr[0]             a=buidHeap(arr[0:len(arr)-x-1])             arr[0:len(arr)-x-1] = a         return arr     arr = buidHeap(arr) return takeout(arr) 

最后是先构堆，然后返回取堆的结果，不到30行代码，和百度百科里的一样整洁！😁

接下来，开始学习比较简单的——归并排序（真的简单吗）

归并排序

归并排序简介：传送门

这个动图没有太好，看一下这个
和堆排序一样，可以总结出两步：
分、并
先把他分成一个一个小数组，比如[1,2,3,4,5,6]要给他分成[1],[2],[3],[4],[5],[6]。，把他们包在一个数组里返回、
紧接着，把他们拼起来把相邻的两个数组的第一个比较，小的移动到新的数组的最后（append）。、
接下来，重点来了！

重点

分

我们用递归来分，既然要把他包在一个数字里，那么我们就创建一个数组：a

def branch(arr):  a = [] 

如果分到了长度小于2，就把他加入到a里面。如果不是，那么就调用branch函数两次，第一次是左边的数组，第二次是右边的，然后返回就行了。：

def MergeSort(arr):     a = [] def branch(arr): if len(arr)<2:             a.append(arr) return         m = int(len(arr)/2) #中间的下标         branch(arr[:m]);branch(arr[m:]) #两次 return a 

效果 如下：

很好，您已经完成了一大半了！

给大家留一道思考一题：为了防止递归栈溢出，我们应该设置递归最大层为多少呢？

并

很简单，比较第一个：

a = [] #临时数组，返回这个 if arr1[0]>=arr2[0]: #如果第二个数组小，删掉，然后把他放到a的最后面     a.append(arr2[0])     arr2.pop(0) else:     a.append(arr1[0]) #右边大的情况     arr1.pop(0) 

如果有一个数组已经被删完了，那么就返回a加上另外一个数组：

if len(arr1)==0: return a+arr2 elif len(arr2)==0: return a+arr1 

最后弄成一个函数：

 def merge(arr1,arr2):         a = [] while True: #要一直分 if len(arr1)==0: return a+arr2             elif len(arr2)==0: return a+arr1             if arr1[0]>=arr2[0]:                 a.append(arr2[0])                 arr2.pop(0) else:                 a.append(arr1[0])                 arr1.pop(0) 

调用函数：

 while True:         a = [] #临时数组 if len(arr)==1: return arr[0] #如果已经归并到了只有一个数组了，就返回 for x in range(0, len(arr), 2): try:                 a.append(merge(arr1=arr[x],arr2=arr[x+1])) #很正常的归并 except:                 a.append(arr[x]) #如果末尾只有1个数组了，那么直接加上去         arr=a    #更新arr 

封装

还是直接复制，无注释。😅

def MergeSort(arr):     a = [] def branch(arr): if len(arr)<2:             a.append(arr) return None         m = int(len(arr)/2)         branch(arr[:m]);branch(arr[m:]) return a     def merge(arr1,arr2):         a = [] while True: if len(arr1)==0: return a+arr2             elif len(arr2)==0: return a+arr1             if arr1[0]>=arr2[0]:                 a.append(arr2[0])                 arr2.pop(0) else:                 a.append(arr1[0])                 arr1.pop(0)      arr = branch(arr) #分 while True:         a = [] if len(arr)==1: return arr[0] for x in range(0, len(arr), 2): try:                 a.append(merge(arr1=arr[x],arr2=arr[x+1])) except:                 a.append(arr[x])         arr=a 

好了！接下来讲解：快速排序！

我个人认为快速排序并不难，一起看看吧！

快速排序

快速排序简介：传送门

这张图比较好，就是随机找个基准数，然后比基准数小的往左移，否则往右移。然后排序这两边的。这可以用：递归！
先导入随机模块：

from random import randrange 

然后，随机取值：

pivotIndex = randrange(0,len(arr)) #arr是数组 pivot = pivot = arr[pivotIndex] 

然后，为了让遍历数组是不用每一次都检查是否是基准值，因此，我们把基准值删了：

arr.pop(pivotIndex) 

创建两个数组，一个放比基准值大的，一个放比基准值小的：

small = [] big = [] 

遍历数组：

for x in range(0,len(arr)): if arr[x]<=pivot:         small.append(arr[x]) else:         big.append(arr[x]) 

然后再调用快速排序来排序big，small两个数组最后返回排序好的small+基准值+排序好的big：

return quikeSort(small)+[pivot]+big 

弄成函数：

from random import randrange def quikeSort(arr): if len(arr)<2: return arr     pivotIndex = randrange(0,len(arr))     pivot = arr[pivotIndex]     arr.pop(pivotIndex)     small = []     big = [] for x in range(0,len(arr)): if arr[x]<=pivot:             small.append(arr[x]) else:             big.append(arr[x]) return quikeSort(small)+[pivot]+big  

完美！！！

接下来，简单地讲解一下深度优先搜索和广度优先搜索（没有代码，抱歉😥）

广度优先搜索和深度优先搜索

广度优先搜索：步步为营，每次每个都前进一格
深度优先搜索：搜完一个再一个
看这幅图就懂了。

由于树这种结构，有太多种了，就先科普一下，以后再详解！
这种搜索应用在哪呢？答案是：我们搜索文件的时候。

没错，每一个目录就是一个节点！

结语

这是第二版了，算法明显变难了不少……希望大家能听懂，有问题欢迎问我，有时间的话我会及时回复的！