Python实现简单的算法

待我称王封你为后i 2023-02-19 14:27 13阅读 0赞

# 四个简单排序 + 图解(冒泡、选择、插入、快速) #

##### 1. 冒泡排序 #####

> 每次循环都将最大的数字放到列表最后  
> ![在这里插入图片描述][aHR0cHM6Ly9pbWFnZXMyMDE3LmNuYmxvZ3MuY29tL2Jsb2cvODQ5NTg5LzIwMTcxMC84NDk1ODktMjAxNzEwMTUyMjMyMzg0NDktMjE0NjE2OTE5Ny5naWY_pic_center]

def bubble_sort(arr):
    		length = len(arr)
    		for i in range(length - 1):
    			for j in range(length - i - 1):
    				if arr[j] > arr[j+1]:
    					arr[j], arr[j+1] = arr[j+1], arr[j]
    		return arr

##### 2. 选择排序 #####

> 选择最小的那个数字，更换位置  
> ![在这里插入图片描述][aHR0cHM6Ly9pbWFnZXMyMDE3LmNuYmxvZ3MuY29tL2Jsb2cvODQ5NTg5LzIwMTcxMC84NDk1ODktMjAxNzEwMTUyMjQ3MTk1OTAtMTQzMzIxOTgyNC5naWY_pic_center]

def choice_sort(arr):
    	    length = len(arr)
    	    for i in range(length - 1):
    	        least = i
    	        for j in range(i + 1, length):
    	            if arr[j] < arr[least]:
    	                least = j
    	        arr[i], arr[least] = arr[least], arr[i]
    	    return arr

##### 3. 插入排序 #####

>  *  从第一个元素开始，该元素可以认为已经被排序；
>  *  取出下一个元素，在已经排序的元素序列中从后向前扫描；
>  *  如果该元素（已排序）大于新元素，将该元素移到下一位置；
>  *  重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
>  *  将新元素插入到该位置后；
>  *  重复步骤2~5。  
>     ![在这里插入图片描述][aHR0cHM6Ly9pbWFnZXMyMDE3LmNuYmxvZ3MuY29tL2Jsb2cvODQ5NTg5LzIwMTcxMC84NDk1ODktMjAxNzEwMTUyMjU2NDUyNzctMTE1MTEwMDAwMC5naWY_pic_center]

def insert_sort(arr):
    	    length = len(arr)
    	    for i in range(length):
    	        index = i
    		    while index:
    		        if index and arr[index-1] > arr[index]:
    		            arr[index - 1], arr[index] = arr[index], arr[index - 1]
    		        index -= 1
    	    return arr

##### 4. 快速排序 #####

> 个人觉得快排是最好理解的，就是利用递归原理，每次分成两个列表，依次向下排序，看代码就应该可以理解了。  
> ![在这里插入图片描述][aHR0cHM6Ly9pbWFnZXMyMDE3LmNuYmxvZ3MuY29tL2Jsb2cvODQ5NTg5LzIwMTcxMC84NDk1ODktMjAxNzEwMTUyMzA5MzYzNzEtMTQxMzUyMzQxMi5naWY_pic_center]

def fast_sort(arr):
    		if len(arr) <= 1:
    			return arr
    		else:
    			left, right = [], []
    			pivot = arr.pop()
    			for i in arr:
    				if i > pivot:
    					right.append(i)
    				else:
    					left.append(i)
    			return fast_sort(left) + [pivot] + fast_sort(right)

# 查找(二分) #

##### 二分查找 #####

def binary_search(arr, target):
    		length = len(arr)
    		# start， end是索引(index)
    		start = 0
    		end = length - 1
    		while start <= end:
    			mid = (start + end) // 2  # 找到中间数的索引(index)
    			if arr[mid] > target:	  # 如果中间这个数大于目标值，则缩短end的索引
    				end = mid - 1
    			elif arr[mid] < target:   # 反之，则增加start的索引
    				start = mid + 1
    			else:					  # 如果相等，则输出
    				return mid

[aHR0cHM6Ly9pbWFnZXMyMDE3LmNuYmxvZ3MuY29tL2Jsb2cvODQ5NTg5LzIwMTcxMC84NDk1ODktMjAxNzEwMTUyMjMyMzg0NDktMjE0NjE2OTE5Ny5naWY_pic_center]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE3LmNuYmxvZ3MuY29tL2Jsb2cvODQ5NTg5LzIwMTcxMC84NDk1ODktMjAxNzEwMTUyMjMyMzg0NDktMjE0NjE2OTE5Ny5naWY#pic_center
[aHR0cHM6Ly9pbWFnZXMyMDE3LmNuYmxvZ3MuY29tL2Jsb2cvODQ5NTg5LzIwMTcxMC84NDk1ODktMjAxNzEwMTUyMjQ3MTk1OTAtMTQzMzIxOTgyNC5naWY_pic_center]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE3LmNuYmxvZ3MuY29tL2Jsb2cvODQ5NTg5LzIwMTcxMC84NDk1ODktMjAxNzEwMTUyMjQ3MTk1OTAtMTQzMzIxOTgyNC5naWY#pic_center
[aHR0cHM6Ly9pbWFnZXMyMDE3LmNuYmxvZ3MuY29tL2Jsb2cvODQ5NTg5LzIwMTcxMC84NDk1ODktMjAxNzEwMTUyMjU2NDUyNzctMTE1MTEwMDAwMC5naWY_pic_center]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE3LmNuYmxvZ3MuY29tL2Jsb2cvODQ5NTg5LzIwMTcxMC84NDk1ODktMjAxNzEwMTUyMjU2NDUyNzctMTE1MTEwMDAwMC5naWY#pic_center
[aHR0cHM6Ly9pbWFnZXMyMDE3LmNuYmxvZ3MuY29tL2Jsb2cvODQ5NTg5LzIwMTcxMC84NDk1ODktMjAxNzEwMTUyMzA5MzYzNzEtMTQxMzUyMzQxMi5naWY_pic_center]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE3LmNuYmxvZ3MuY29tL2Jsb2cvODQ5NTg5LzIwMTcxMC84NDk1ODktMjAxNzEwMTUyMzA5MzYzNzEtMTQxMzUyMzQxMi5naWY#pic_center