数据结构（python）---- 排序与搜索算法

一、排序算法的稳定性

二、排序算法

1.冒泡排序

时间复杂度：O(n²)，
优化时间复杂度：O(n)
稳定性：稳定

冒泡排序的分析
游标从前往后只进行两两比较，第一遍只确定下了最后一个是最大的，不去记忆其他数，在开始第二遍确定倒数第二个数是次大的。

冒泡：每遍历一次，相当于有个最大值冒出来。

def bubble_sort(alist):'''冒泡排序思想：len(alist)=n1.内层循环：每一遍从前往后遍历，第一遍，i走n-1次进行两两比较，for i in (0,n-1)2.外曾循环：遍历的次数 j，for j in range(n-1)内外曾循环的关系分析：i range(0,n-1) j=0i range(0,n-1-1) j=1i range(0,n-1-2) j=2即：for j in range(n-1):for i in range(n-1-j):优化：排序算法本身的时间复杂度未O(n²)，对其优化：j range(n-1),当j<n-1次就已经满足从小到大排列后，就不用再遍历了引入一个count，元素交换一次，count+1，if count=0，则直接返回'''n=len(alist)for j in range(n-1):count=0for i in range(n-1-j):if alist[i]>alist[i+1]:alist[i],alist[i+1]=alist[i+1],alist[i]count += 1if count==0:returnif __name__=="__main__":liu=[32,34,87,34,56,56]# liu=[1,2,3,8,5,4,9,10]print(liu)bubble_sort(liu)print(liu)
# [32, 34, 87, 34, 56, 56]
# [32, 34, 34, 56, 56, 87]

2.选择排序

时间复杂度：选择排序的时间复杂度为O(n²)。目前没有最优复杂度方法
稳定性：不稳定（考虑升序），
列表liu=[（26，2），16，17，15，（26，1），11，9]，第一个26与后面比较是最大的，则与最后的元素9交换位置，这样的话，不稳定。

选择排序分析：

'''
选择排序思想：
len(alist)=n
i:序列中最小元素的索引，从0开始
j：循环的次数 range(0，n-1)（最后一个已经是最大值）1.内层循环：设置0为最小元素的索引，用i(range(0+1,n))遍历剩下的序列，若值小于0索引，则设置最小交换元素索引为i，然后在本次内层循环结束后交换位置。
2.外曾循环：遍历的次数 j，for j in range(n-1)内外曾循环的关系分析：
j=0
min=0  i--(0+1,n)
j=1
min=1  i--(1+1,n)
j=2
min= 2 i--(2+1,n)'''def select_sort(alist):n=len(alist)for j in range(n-1):min_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__":liu=[32,34,87,34,56,56]print(liu)select_sort(liu)print(liu)
#[32, 34, 87, 34, 56, 56]
#[32, 34, 34, 56, 56, 87]

3.插入排序算法

选择排序和插入排序算法的区别：
选择排序：前面序列的最后一个是固定放元素的位置，和后面元素比较，操作后面的元素
插入算法：用后面序列的第一个元素和前面序列从后往前一一比较，操作的是前面的序列

插入排序时间复杂度：O(n²)
最有时间复杂度：O(n)
稳定性：稳定

插入算法分析：

'''
插入排序算法思想：
前面为有序序列  后面是无序序列
用后面序列的第一个与前面的序列从后往前比较，一个一个比骄，然后交换位置，插入到合适的位置（前面序列从小往大）1.内部循环：i和i-1的元素值进行比较大小，如果小交换位置，并设置i=i-1
2.外部循环：j从第二个元素开始循环，家盯第一个是最小的
'''
def insert_sort(alist):'''插入排序算法'''n=len(alist)for j in range (1,n-1):i=jwhile i > 0:if alist[i] < alist[i-1]:alist[i],alist[i-1]=alist[i-1],alist[i]i-=1else:breakif __name__=="__main__":liu=[32,34,87,34,56,56]print(liu)insert_sort(liu)print(liu)
# [32, 34, 87, 34, 56, 56]
# [32, 34, 34, 56, 87, 56]

4.希尔排序

1.希尔排序的稳定性：不稳定
希尔排序最优时间复杂度：根据步长序列不同而不同
希尔排序最坏时间复杂度：O(n²)

2.希尔排序分析：

1.设置一个间隙，进行第一次循环，按照间隙及间隙索引的倍数将序列分成多个序列，将每个序列按照插入排序从小到大排列，然后插入成一排
2.缩小间隙，及进行第二次、第三次循环。。。

'''
希尔排序：
和插入排序算法代码差不多
1.设置一个间隙，进行第一次循环，按照间隙及间隙索引的倍数将序列分成多个序列，将每个序列按照**插入排序**从小到大排列，然后插入成一排
2.缩小间隙，及进行第二次、第三次循环。。。
'''
def shell_sort(alist):n=len(alist)gap=n//2#取整#gap变化到0之前，插入算法执行的次数while gap>0:#插入算法，与普通的插入算法不同的是gapfor 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:breakif __name__=="__main__":liu=[32,34,87,34,56,56]print(liu)shell_sort(liu)print(liu)
# [32, 34, 87, 34, 56, 56]
# [32, 34, 34, 56, 87, 56]

5.快速排序（敲重点*）

1.快速排序分析：
首先是要找到序列第一个元素（比如8）再排好序后所在的位置，达到的效果是：8前面的序列都比8小，8后面的元素都比8大。

1. 分区操作：low游标和high游标同时移动，low开始指向第一个元素8从左往右走过的元素都小于8，high开始指向最后一个元素从右往左走过的元素都大于8。mid_value变量指向第一个元素8，则low空出来，high遇到小于8的停下来，将指向的元素交给low，low开始往后走遇到大于8的停下来，将指向的元素交给high，high开始往前走，不断执行。
2. 当循环结束后，递归地(自己调用自己)对8两边的序列分别再执行快速排序。

递归修改代码思想：
当找到第一个元素在排好序序列中的位置后，分别递归地执行此元素前面和后面序列，为了保证递归后的序列和原序列保持使用同一个索引，传入值为：(原序列，要执行操作的初始序列，结束序列)，(alist,first,last),（alist,0,low-1),(alist,low+1,n-1)
递归终止条件：当first>=last时终止递归

def quick_sort(alist,first,last):'''快速排序算法'''if first >= last:  #递归执行终止条件returnmid_value=alist[first]low=firsthigh=lastwhile low<high:#high左移while low < high and alist[high]>=mid_value:high-=1alist[low]=alist[high]while low < high and alist[low]<mid_value:low+=1alist[high]=alist[low]#从循环退出时，low==highalist[low]=mid_value#对low左边的列表执行快速排序quick_sort(alist,first,low-1)#对low右边的列表执行快速排序quick_sort(alist,low+1,last)if __name__=="__main__":liu=[32,34,87,34,56,77,89,25,42]print(liu)quick_sort(liu,0,len(liu)-1)print(liu)
# [32, 34, 87, 34, 56, 77, 89, 25, 42]
# [25, 32, 34, 34, 42, 56, 77, 87, 89]

2.快速排序的时间复杂度和稳定性

第1次递归执行2个序列 ，2(1次幂)
第2次递归执行4个序列 ，2(2次幂)
第3次递归执行8个序列 ，2(3次幂)
…

len(alist)=2(的几次幂) 就执行几次递归
执行次数=log(len(alist)) 以2为底
log n以2为底 指的是：2的几次幂=n

则快速排序法最优时间复杂度为：O(nlogn) (以2为底)
快速排序法最坏时间复杂度为O(n²)
快速排序法稳定性：不稳定

6.归并排序算法

用的少

归并排序法最优时间复杂度为：O(nlogn) (以2为底)
归并排序法最坏时间复杂度为O(nlogn) (以2为底)
归并排序法稳定性：稳定
与其他排序算法相比，其他排序算法都是在元列表的基础上排序，归并排序算法会生成一个新的列表返回，需要一个与原列表同大的空间存储，产生额外的开销

'''
归并排序算法
先递归的将序列分成两部分，直到序列只有一个元素，
开始合并序列：按照从到大顺序
'''
def merge_sort(alist):n=len(alist)if n<=1:return alistmid =n//2#left  采用归并排序后形成的新列表left_li=merge_sort(alist[:mid])#right  采用归并排序后形成的新列表right_li=merge_sort(alist[mid:])#合并两个列表为一个新的整体# merge（left,right_li）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__":liu = [32, 34, 87, 34, 56, 77, 89, 25, 42]# liu = [32, 34, 87, 56, 77, 89]print(liu)soft_liu=merge_sort(liu) #soft_liu用来接收排序序列print(soft_liu)# [32, 34, 87, 34, 56, 77, 89, 25, 42]
# [25, 32, 34, 34, 42, 56, 77, 87, 89]

归并排序算法分析：

常简的排序算法效率比较

三、搜索算法---- 二分查找

二分查找最优时间复杂度：O(1)
最坏时间复杂度：O(logn)

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 Falsedef 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__":liu = [25, 32, 34, 34, 42, 56, 77, 87, 89]  #必须是顺序列表print(binary_search(liu,89))print(binary_search(liu,88))print(binary_search_2(liu,89))print(binary_search_2(liu,88))# True
# False
# True
# False