一、排序与搜索
1、冒泡排序
def bubble_sort(alist):'''冒泡排序'''n=len(alist)for j in range(n-1):##从0到n-2for i in range(0,n-j-1): ##包头不包尾###班长从头走到尾if alist[i]>alist[i+1]:alist[i],alist[i+1]=alist[i+1],alist[i]if __name__=='__main__':li=[54,26,93,17,77,31,44,55,20]print(li)bubble_sort(li)print(li)
方法二
for j in range(len(alist)-1,0,-1)for i in range(j)
方法 一 的时间复杂度 o（n^2）
plus版
def bubble_sort(alist):'''冒泡排序'''n=len(alist)for j in range(n-1):##从0到n-2for i in range(0,n-j-1): ##包头不包尾###班长从头走到尾count=0if alist[i]>alist[i+1]:alist[i],alist[i+1]=alist[i+1],alist[i]count+=1if 0==count:returnif __name__=='__main__':li=[1,2,4,3,5,6]print(li)bubble_sort(li)print(li)
改进之后最优时间复杂度O(n)
二、选择排序法
def select_sort(alist):"选择排序"n=len(alist)for j in range(0,n-1):##j:0~n-2min_index=jfor i in range(j+1,n):if alist[min_index]>alist[i]:min_index=ialist[j],alist[min_index]=alist[min_index],alist[j]if __name__=='__main__':li=[54,226,93,17,77,31,44,55,20]print(li)select_sort(li)print(li)
[54, 226, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 31, 44, 54, 55, 77, 93, 226]
时间复杂度 O（n^2）
三、插入排序
alist=[54,26,93,17,77,31,44,55,20]def insert_sort(alist):"插入算法"n=len(alist)#外层循环代表的是从右边的无序序列中取出多少个元素执行这样的过程for j in range(1,n):#'j=【1,2，……n-1】'i=j#"i代表代表内层循环起始值"#执行从右边的无序序列中取出第一个元素，即i位置的元素，然后将其插入到前面的正确位置中while i>0:if alist[i] <alist[i-1]:alist[i],alist[i-1]=alist[i-1],alist[i]i-=1else:breakif __name__=='__main__':li=[54,26,93,17,77,31,44,55,20]print(li)insert_sort(li)print(li)
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
稳定
最坏时间复杂度o(n^2)
最优时间复杂度O(n^2)
四、希尔排序
希尔排序是插入排序的改进版。希尔排序是非稳定算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序。随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
def shell_sort(alist):"""希尔排序"""#每次按折半的方式#gap=4n=len(alist)gap=n//2 #整除while gap>=1:##gap>0#gap变化0之前，插入算法执行的次数 #插入算法，与普通的插入算法的区别就是gap步长for j in range(gap,n):i=jwhile i>0:if alist[i]<alist[i-gap]:alist[i],alist[i-gap]=alist[i-gap],alist[i]i-=gapelse:break#缩短gap步长gap//=2if __name__=='__main__':li=[54,26,93,17,77,31,44,55,20]print(li)shell_sort(li)print(li)
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
最坏时间复杂度O(n^2)
五、快速排序（重要，必须掌握）
快速排序，有称划分交换排序。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
#!usr/bin/env python# -*- coding:utf-8 _*-"""@author: JMS@file: my13.py@time: /05/17@desc:"""def quick_sort(alist,first,last):mid_value=alist[first]low=firsthigh=lastif first>=last:returnwhile low<high:while low<high and alist[high]>=mid_value:#high左移high-=1alist[low]=alist[high]#low+=1while low<high and alist[low] < mid_value:#low右移low+=1alist[high]=alist[low]#high-=1##从循环退出时,low==highalist[low]=mid_value#对Low左边的列表执行快速排序quick_sort(alist,first,low-1)#对Low右边的列表快速排序quick_sort(alist,low+1,last)if __name__=='__main__':li=[54,26,93,17,77,31,44,55,20]print(li)quick_sort(li,0,len(li)-1)print(li)
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
最优时间复杂度O(nlgn)
最坏时间复杂度O（n^2）
稳定性：不稳定
六、归并排序
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再组合数组。
将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
def merge_sort(alist):"""归并排序"""###拆分n=len(alist)if n<=1:return alistmid=n//2###left 采用归并排序后形成的有序的新的列表，right同left_li =merge_sort(alist[:mid])right_li=merge_sort(alist[mid:])###合并#将两个有序的子序列合并为一个新的整体#merge(left,right)left_pointer,right_pointer=0,0result=[]while left_pointer<len(left_li) and right_pointer<len(right_li):if left_li[left_pointer]<right_li[right_pointer]:result.append(left_li[left_pointer])left_pointer+=1else:result.append(right_li[right_pointer])right_pointer+=1result+=left_li[left_pointer:]result+=right_li[right_pointer:]return resultif __name__=='__main__':li=[54,26,93,17,77,31,44,55,20]print(li)sorted_li=merge_sort(li)print(li)print(sorted_li)
最坏时间复杂度（nlogn）
最优时间复杂度（nlogn）
稳定性：稳定
七、搜索
二分查找
def binary_search(alist,item):#一个有序的序列，递归版n=len(alist)if n>0:mid=n//2if alist[mid]==item:return Trueelif item<alist[mid]:return binary_search(alist[:mid],item)else:return binary_search(alist[mid+1:],item)return Falseif __name__=='__main__':li=[17, 20, 26, 31, 44, 54, 55, 77, 93]print(binary_search(li,55))print(binary_search(li, 100))
True
False
非递归
def binary_search_2(alist,item):#非递归版本,二分查找n=len(alist)first=0last=n-1while first<=last:mid=(first+last)//2if alist[mid]==item:return Trueelif item<alist[mid]:last=mid-1else:first=mid+1return Falseif __name__=='__main__':li=[17, 20, 26, 31, 44, 54, 55, 77, 93]print(binary_search_2(li,55))print(binary_search_2(li, 100))
True
False
最优时间复杂度O(1)
最坏时间复杂度O(logn)
