十分详细！python手写经典算法详解（一）

今天，我将给大家带来5个经典算法，并且详细的解说。语言为python3

---

前言

2020/6/2更：
考虑到阅读量较大，我特地将源码放在了这个链接中

---

今天，我讲给大家讲解的算法是：

• 冒泡排序
• 选择排序
• 插入排序
• 数组的查找：线性查找，二分查找

第二版将可能讲解比较难的：

• 归并排序
• 快速排序
• 堆排序
• 树的搜索：广度优先和深度优先。

火热通告！第二版发布了！！链接：这里!

特别声明：本文中的代码**完全由本人编写**，绝对不存在抄袭等现象。如对代码有任何问题，欢迎在评论区中指出。转载请注明出处，谢谢!

由于本人文笔不是很好😉 所以，有什么问题欢迎指出！

不废话了，开始算法之旅吧！

冒泡排序

冒泡排序简介：传送门

可以发现，总共需要循环数组的长度-2次。而且每排序n次，末尾就会有n个数不用排序。我们一步一步来，首先先来个函数，并且加上循环

def Bubble(arr):
    for n in range(len(arr)-2):
    	pass

然后，让x从零开始与下标为x+1的比较，一直比较到已经排序好的

def Bubble(arr):
    for n in range(len(arr)-2):
        for x in range(0,len(arr)-1-n):	#减一是因为要和他的下标加一的数比较，避免下标溢出
            a = arr[x]
            b = arr[x+1]
            if a>b:
                arr[x],arr[x+1]=arr[x+1],arr[x]	#交换

不要忘记返回噢！

def Bubble(arr):
    for n in range(len(arr)-2):
        for x in range(0,len(arr)-1-n):
            a = arr[x]
            b = arr[x+1]
            if a>b:
                arr[x],arr[x+1]=arr[x+1],arr[x]
    return arr

好了，冒泡排序就讲解到这里！

最后，给大家留一道思考题，能不能每一次都判断一下数组有没有排序好呢？时间复杂度呢？

选择排序

选择排序简介：传送门

就是选择出最小的，把他放在已经排序好的index的右面。需要循环数组长度次。
首先，先写一个找出数组最小数的函数：
先假设下标为0的数是最小的，然后后面每发现一个小于当前最小数的数，就更新一次，最后返回。
十分简单，所以直接上代码：

def FindMinNum(arr):
    minIndex = 0
    for x in range(0,len(arr)):
        if arr[x]<arr[minIndex]:
            minIndex = x
    return minIndex

然后，就开始编写选择排序：
由于第几次前面就会有几个排好序的数，所以不用单独弄变量了。先来一个循环

def Selection(arr):
    for x in range(0,len(arr)):
    	pass

然后，找出最小的数

注意这里必须不包含前面的已经排好序的数，所以：

def Selection(arr):
    for x in range(0,len(arr)):
        a = FindMinNum(arr[x:])		#已经排好序的数后面
        arr[a+x],arr[x] = arr[x],arr[a+x]	#交换
    return arr

这就完了？真的？没错，就那么简洁。

上源码：

def FindMinNum(arr):
    minIndex = 0
    for x in range(0,len(arr)):
        if arr[x]<arr[minIndex]:
            minIndex = x
    return minIndex
    
def Selection(arr):
    for x in range(0,len(arr)):
        a = FindMinNum(arr[x:])		#已经排好序的数后面
        arr[a+x],arr[x] = arr[x],arr[a+x]	#交换
    return arr

选择排序就讲解到这里，接下来是插入排序！

插入排序

插入排序简介：传送门

发现，首先假设第一个元素已经排好序了。然后，在没有排序好的中选出最左边的（第一个），与前面的比较，直到最左边（下标为0 ），或比左边的数要大。就停止。

分析一下，这相当于一个while。条件是下标不等于0，而且当大于左边的数（下标不本身小1），就跳出循环。
那就开始咯：

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

大家请注意一下这个迭代的x，他是非常重要的，他可不是用来凑数的，他可是没有排好序的第一个数的下标！
接下来，开始写那个while：

def insertSort(arr):
    for x in range(1,len(arr)):
        while x>0:	#下标等于0就不比较啦！
        	pass

紧接着，判断，与下标为x-1的数比较：

def insertSort(arr):
    for x in range(1,len(arr)):
        while x>0:
            if arr[x]<arr[x-1]:
                arr[x],arr[x-1] = arr[x-1],arr[x]	#交换
                x -= 1	#x = x-1
            else:
                break

加上返回，上源码：

def insertSort(arr):
    for x in range(1,len(arr)):
        while x>0:
            if arr[x]<arr[x-1]:
                arr[x],arr[x-1] = arr[x-1],arr[x]
                x -= 1
            else:
                break
    return arr

好了，本篇的排序算法就到此结束。接下来就是查找了。

数组的查找

线性查找

额……这里不给简介了。相信大家都知道。
说白了就是一个一个找

这……没什么可说的，上源码吧：

def Linear(arr,number):
    for x in range(0,len(arr)):
        if arr[x]==number:
            return x

说一下，如果找不到的话应该return None的，不过没有返回就是return None了。

二分查找

二分查找简介：传送门

注意，这里必须是排好序的数组，然后，选出中间的数，判断要查找的数比它大，还是小。然后，就能判断范围了。范围就是左边的index，右边的index。那中间怎么求呢？那就是数组的长度除以2：

int(len(arr)/2)

那就开始了：

def Binary(arr,number):
    while True:
    	pass

然后求出中间的数，判断范围，如果他就是要找的数，那么就返回。之间上代码了：

def Binary(arr,number):
    while True:
        m = int((l+r)/2)     #Middle index
        n = arr[m]  #Middle number
        if number==n:
            return m
        if number > n:
            l = m
        if number < n:
            r = m

结语

今天的博文就到此结束了！如果您有任何问题，欢迎评论区指出。我会更好的改进文章。

谢谢大家！
转载：https://blog.csdn.net/icaijy/article/details/106430133