我是根据b站上python数据结构里写的
https://www.bilibili.com/video/BV1uA411N7c5?p=19&vd_source=02a4e8285fe8de80a417aeb3344debc0
网上有很多关于堆排的，我这里就不重复了，写点不一样的。
堆排原理，建堆-》出数——》向下调整（我看算法导论里叫维护堆，差不多一个意思）
堆是一种树，有大堆小堆，大堆就是父节点比子节点大.
也就是说，建完堆，堆顶是最大的，每次取堆顶交换数组最后一个（没排序的最后一个），就能排好。
父节点是（子节点-1）//2
左子节点是2父+1,右子节点是2父+2
太多我就不说了，可以看看其他博客，这里说点别的地方没有的。
https://blog.csdn.net/qq_28063811/article/details/93034625/
步骤
1.建堆建堆用向下调整也叫堆维护，建立个大堆
就是重第一非叶子节点开始，循环维护向下调整后，数组就是大堆。
数学证明算法导论中有，我还没看。
大概就是，重一开个小堆开始，向下调整，还挺不好理解的暂时相信它是对的。
向下调整的代码
def sift(li,low,high): i =low #堆顶指针1 j = 2*i+1 # 指针2 tmp = li[low] #需要比较的数 while j<= high: #指针2别出界，出界就停了 if j+1 <=high and li[j+1]>li[j]: #有没有右子节点，有右子节点的话比较，让j指针是大的那个 j = j+1 if tmp < li[j]: # 比较两个指针大小，做出是否交换，和向下 li[i] = li[j] i = j j = 2*i+1 else: li[i] = tmp #发现它是最大的，不用比了，停止，把tmp放在这层 break else: li[i] = tmp #循环完了，没有可以比的了，把tmp放在这
两个
就是两个指针比较，当然每一层实际上是三个数比较
左节点和右节点比较，找到大的，变成j，和tmp比较
如果j大把li[j]的值给到i的位置
如果停止了（可能是到底了，也可能是tmp比下面都大了），总之停止了，就把li[i] =tmp,把tmp放在这就行。
建堆代码
def hip_sort(li): n = len(li) for i in range((n-1-1)//2,-1,-1): sift(li , i, n-1) #每次的low就是每个非叶子节点，一直到0，high就是让它别出界就行，到n-1
先找到最后一个叶子节点，就是最后一个数它的父节点，最后一个数下标是数组长度-1，
它的父节点是(n-1-1)//2
python的//是除法并向下取整，就是啥意思，如果是左 ，减一处2后，应该是个整数，那就是它，
如果是右，减一处2，可能带个0.5，因为是向下取证，那还是它
因为python语法，右括号的-1是不包含-1的，到0,注意一下
2.出数并向下调整for j in range(n-1,0,-1): # 从最后一个数，到倒数第二个（我感觉li[0]没必要和li[0]交换） li[0],li[j] = li[j],li[0] #交换 sift(li,0,j-1) #向下调整，注意一下调整需要的high是j-1，交换完了，需要调整的数组就少了一个数
写的不太好，变革口诀吧
def sift(li,low,high): i =low j = 2*i+1 tmp = li[low] while j<= high: if j+1 <=high and li[j+1]>li[j]: j = j+1 if tmp < li[j]: li[i] = li[j] i = j j = 2*i+1 else: li[i] = tmp break else: li[i] = tmp def hip_sort(li): n = len(li) for i in range((n-1-1)//2,-1,-1): sift(li , i, n-1) for j in range(n-1,0,-1): li[0],li[j] = li[j],li[0] sift(li,0,j-1)
建堆出数加调整，最后非叶子节点调到0.
0和堆的最后一个换，再调整。
一个i一个j双指针，i是根j是它子节点
while一循环，防止出界j小于等于high。
如果有右子节点，选出左右最大数下标。
如果子大于tmp，就交换到i位置。
并子变父，生成新子，否则停止tmp放在i。
停了就把tmp放i那。
