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

前言

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

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

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

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

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

堆排序

堆排序简介：传送门

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

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

构堆，取顶。

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

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

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

父节点下标	子节点下标
0	1，2
1	3，4
2	5，6
……	……

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

---

父节点的下标*2+1等于第一个子节点下标，反过来呢？ 子节点的下标除以二，整数-1，小数直接int。

这里给一个小例子：

    def SonItoFaI(sonindex):	#函数名太怪了，意思是Sonindextofatherindex 😜sonindex = sonindex/2if sonindex==int(sonindex):	#整数减一return sonindex-1else: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:breakif arr[x]>arr[f]:arr[x],arr[f],x = arr[f],arr[x],felse:breakreturn 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] = areturn arr

封装

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

def heapsort(arr):def SonItoFaI(sonindex):	sonindex = sonindex/2if sonindex==int(sonindex):	return sonindex-1else:return int(sonindex)def buidHeap(arr):for x in range(1,len(arr)):while True:f = SonItoFaI(x)if x == 0:breakif arr[x]>arr[f]:arr[x],arr[f],x = arr[f],arr[x],felse:breakreturn arrdef 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] = areturn arrarr = 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)returnm = 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+arr2elif len(arr2)==0:return a+arr1if 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 Nonem = int(len(arr)/2)branch(arr[:m]);branch(arr[m:])return adef merge(arr1,arr2):a = []while True:if len(arr1)==0:return a+arr2elif len(arr2)==0:return a+arr1if 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 arrpivotIndex = 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

完美！！！

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

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

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

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

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

结语

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

谢谢大家！