Python数据结构

各种排序实现

排序思想不做描述。

#冒泡def bubble_sort(alist):for x in range(0,len(alist)-1):isswap = Falsefor y in range(x,len(alist)):# print(x,y)if alist[x] > alist[y]:isswap = Truealist[x] , alist[y] = alist[y] , alist[x]if not isswap:break#选择def selection_sort(alist):for x in range(len(alist)):minindex = xfor y in range(x,len(alist)):if alist[y]<alist[minindex]:minindex = yalist[x],alist[minindex] = alist[minindex],alist[x]#插入def insert_sort(alist):for x in range(1,len(alist)):# 从第二个位置，即下标为1的元素开始向前插入for y in range(x,0,-1):if alist[y] < alist[y-1]:alist[y],alist[y-1] = alist[y-1],alist[y]#快速def quick_sort(alist, start, end):if start >= end:returnmid = alist[start]# print(start,end,mid)l = startr = endwhile l<r:while l<r and alist[r]>mid:r-=1alist[l] = alist[r]while l<r and alist[l]<mid:l+=1alist[r] = alist[l]alist[l] = midquick_sort(alist,start,l-1)quick_sort(alist,l+1,end)#希尔def shell_sort(alist):n = len(alist)gap = n//2while gap>0:for i in range(gap,n):temp = alist[i]j = iwhile j>=gap and alist[j-gap]>temp:alist[j] = alist[j-gap]j-=gapalist[j]=tempgap = gap//2# 归并def merge_sort(alist):"返回更新完成的新的有序列表"if len(alist)<=1:return alistnum = len(alist)//2left = merge_sort(alist[:num])# print(left)right = merge_sort(alist[num:])# print(right)return merge(left,right)def merge(left, right):"返回有序数组"l,r = 0,0nums = []while l<len(left) and r<len(right):if left[l]>right[r]:nums.append(right[r])r+=1else:nums.append(left[l])l+=1while l<len(left):nums.append(left[l])l+=1while r<len(right):nums.append(right[r])r+=1return numsif __name__ == "__main__":alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]# insert_sort(alist)alist = merge_sort(alist)print(alist)

常见排序算法效率比较

搜索

常见搜索方式

顺序查找、二分法查找、二叉树查找、哈希查找

二分法查找

对于有序数组Ologn

def binary_search(alist, item):first = 0last = len(alist)-1while first<=last:midpoint = (first + last)/2if alist[midpoint] == item:return Trueelif item < alist[midpoint]:last = midpoint-1else:first = midpoint+1return Falsetestlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]print(binary_search(testlist, 3))print(binary_search(testlist, 13))