2283-鲁同学

, ,

各种排序实现

#冒泡
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]<alist[minindex]:
minindex = y
alist[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:
return
mid = alist[start]
# print(start,end,mid)
l = start
r = end
while l<r:
while l<r and alist[r]>mid:
r-=1
alist[l] = alist[r]
while l<r and alist[l]<mid:
l+=1
alist[r] = alist[l]
alist[l] = mid
quick_sort(alist,start,l-1)
quick_sort(alist,l+1,end)

#希尔
def shell_sort(alist):
n = len(alist)
gap = n//2
while gap>0:
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 l<len(left) and r<len(right):
if left[l]>right[r]:
nums.append(right[r])
r+=1
else:
nums.append(left[l])
l+=1
while l<len(left):
nums.append(left[l])
l+=1
while r<len(right):
nums.append(right[r])
r+=1
return nums

if __name__ == "__main__":
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
# insert_sort(alist)
alist = merge_sort(alist)
print(alist)


搜索

二分法查找

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))


Vieu3.3主题

Q Q 登 录