算法中基础中的基础，排序/二分查找
排序
1.快排QuickSort
def quicksort(nums):
return QS(nums,0,len(nums)-1)
def QS(nums,left,right):
if left >= right:
return nums
key = nums[left]
lp = left
rp = right
while lp < rp:
while nums[rp] >= key and lp<rp:
rp -= 1
while nums[lp] <= key and lp<rp:
lp += 1
nums[rp],nums[lp] = nums[lp],nums[rp] # 碰到左右需要交换的元素时交换
nums[left],nums[lp] = nums[lp],nums[left] # 此时lp = rp，与key元素交换，key在中间
QS(nums,left,lp-1)
QS(nums,lp+1,right)
return nums
if __name__ == '__main__':
lst = [5,4,6,2,7,3,8]
print(quicksort(lst))
归并排序
def merge_sort(lst):
if len(lst) <=1:
return lst
else:
middle = len(lst)//2
left = lst[:middle]
right = lst[middle:]
merge_sort(left)
merge_sort(right)
i,j,k = 0,0,0
while i < len(left) and j< len(right):
if left[i] <= right[j]:
lst[k] = left[i]
i = i + 1
else:
lst[k] = right[j]
j = j + 1
k = k + 1
while i < len(left):
lst[k] = left[i]
i += 1
k += 1
while j < len(right):
lst[k] = right[j]
j += 1
k += 1
return lst
堆排序
def shiftdown(lst,i,n):
h = 2 * i + 1
while h <= n:
if h + 1 <= n and lst[h+1] > lst[h]:
h = h + 1
if lst[h] > lst[i]:
lst[i],lst[h] = lst[h],lst[i]
else:
break
i = h
h = 2 * i + 1
def heapSort(lst):
length = len(lst)
for j in range(length//2 - 1,-1,-1):
shiftdown(lst,j,length-1)
print('lst_tmp',lst)
for i in range(length-1,0,-1):
lst[0],lst[i] = lst[i],lst[0]
shiftdown(lst,0,i-1)
print('sorted lst',lst)
1. 二分查找
#coding=utf-8
def bi_search(nums,target):
left = 0
right = len(nums) - 1
res = []
while left <= right:
mid = (left + right) // 2 #left + (right - left) //2
#print(left,right)
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid -1
elif nums[mid] < target:
left = mid + 1
return None
