Python 堆排序
堆排序有点像先二分法找极大值，再冒泡排序：
# 假定数组最后一位是根节点，其他部分平分为分支节点
# 经过一次OneHeapSort，找到最大值并放到根节点
defOneHeapSort(list, l, r):
if r-l<=0:
return
if r-l==1and list[l]>list[r]:
list[l],list[r]= list[r],list[l]
else:
middle = l +(r-l-1)//2
OneHeapSort(list, l, middle)
OneHeapSort(list, middle+1, r-1)
if list[middle]>list[r]:
list[middle],list[r]= list[r],list[middle]
if list[r-1]>list[r]:
list[r-1],list[r]= list[r],list[r-1]
# 依次将最大值放到数组的后面
def heapSort(list):
for i in range(len(list)-1,0,-1):
OneHeapSort(list,0, i)
list =[1,10,8,200,50,4]
heapSort(list)
print(list)# [1,4,8,10,50,200]
稍微改下有点像归并排序，只不过归并排序是给子序列排序，而这个是每轮循环找出最大值
defOneHeapSort(list, l, r):
if r-l<=0:
return
else:
middle = l +(r-l-1)//2
OneHeapSort(list, l, middle)
OneHeapSort(list, middle+1, r)
if list[middle]>list[r]:
list[middle],list[r]= list[r],list[middle]
# 依次将最大值放到数组的后面
def heapSort(list):
for i in range(len(list)-1,0,-1):
OneHeapSort(list,0, i)
list =[1,10,8,200,50,4]
heapSort(list)
print(list)# [1,4,8,10,50,200]
