2.排序
归并排序：
先递归 再分数组排序
''' 将 alist 拆分为 leftalist 和 rightalist 两个数组递归 '''
def merge_sort(alist):
if (len(alist) <= 1):
return alist
mid = len(alist)//2
leftalist = merge_sort(alist[:mid])
rightalist = merge_sort(alist[mid:])
return merge(leftalist,rightalist)
''' 将拆分后的两个子列表进行排序合并 '''
def merge(lalist,ralist):
lalist_point,ralist_point = 0 , 0
result = []
''' 排序 '''
while lalist_point < len(lalist) and ralist_point < len(ralist):
if lalist[lalist_point] <= ralist[ralist_point]:
result.append(lalist[lalist_point])
lalist_point += 1
else:
result.append(ralist[ralist_point])
ralist_point += 1
''' 合并 '''
if lalist_point == len(lalist):
result += ralist[ralist_point:]
else:
result += lalist[lalist_point:]
return result
快速排序：
先分数组 再递归
''' 分治法'''
def quicksort(listone):
if len(listone) < 1:
return listone
else:
num = listone[0]
less = [i for i in listone[1:] if i < num]
rest = [i for i in listone[1:] if i > num]
return quicksort(less)+[num]+quicksort(rest)
listone = [3,4,6,1,2,5]
print(quicksort(listone))
def QuickSort(nums,left,right):
if left>=right:
return nums
baseNumber=nums[left]
i=left
j=right
while i!=j:
while j>i and nums[j]>=baseNumber: //j哨兵 从右往左 找到一个比 baseNumber 小的数
j-=1
while i[InvalidCharacterError: "nums[i]<" did not match the Name production]
return nums