- 各种排序实现
- 常见排序算法效率比较
- 搜索
- 二分法查找
排序思想不做描述。
#冒泡
def bubble_sort(alist):
for x in range(0,len(alist)-1):
isswap = False
for y in range(x,len(alist)):
# print(x,y)
if alist[x] > alist[y]:
isswap = True
alist[x] , alist[y] = alist[y] , alist[x]
if not isswap:
break
#选择
def selection_sort(alist):
for x in range(len(alist)):
minindex = x
for y in range(x,len(alist)):
if alist[y]= end:
return
mid = alist[start]
# print(start,end,mid)
l = start
r = end
while lmid:
r-=1
alist[l] = alist[r]
while l0:
for i in range(gap,n):
temp = alist[i]
j = i
while j>=gap and alist[j-gap]>temp:
alist[j] = alist[j-gap]
j-=gap
alist[j]=temp
gap = gap//2
# 归并
def merge_sort(alist):
"返回更新完成的新的有序列表"
if len(alist)<=1:
return alist
num = len(alist)//2
left = merge_sort(alist[:num])
# print(left)
right = merge_sort(alist[num:])
# print(right)
return merge(left,right)
def merge(left, right):
"返回有序数组"
l,r = 0,0
nums = []
while lright[r]:
nums.append(right[r])
r+=1
else:
nums.append(left[l])
l+=1
while l
常见排序算法效率比较
搜索
常见搜索方式
顺序查找、二分法查找、二叉树查找、哈希查找
二分法查找
对于有序数组Ologn
def binary_search(alist, item):
first = 0
last = len(alist)-1
while first<=last:
midpoint = (first + last)/2
if alist[midpoint] == item:
return True
elif item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1
return False
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))
