目录
知识积累：?
具体：?
?第一步：建堆
具体思路看注解
我们要大根堆
大的在上面
def sift(li,low,hight):
'''
li ； 列表
low ： 根节点的位置
hight : 堆最后一个元素的位置
return
'''
i = low
j = 2*i +1
tem = li[low] #记录堆顶
while j <= hight: #只要j位置有数字
if j+1 <= hight and li[j+1] > li[j]: #如果右孩子大于左孩子
j = j + 1 #指向右孩子
if li[j] > tem: #下一层大于当前的
li[i] = li[j] #交换值
i = j #再往下看一层
j = 2 * i + 1 #重置j
else: #tem更大，把tem放在i的位置上
li[i] = tem
break
else:
li[i] = tem第二步：主体
从下往上开始找父节点 建堆
?
def heap_sort(li):
n = len(li)
#建堆
for i in range((n-2)//2,-1,-1):
#i表示建堆的时候调整部分的下标
sift(li,i,n-1)
#建堆完成
print(li)第三步：验证
li = [i for i in range(100)]
import random
random.shuffle(li)
heap_sort(li)
结果?
第四步: 将堆释放
for i in range(n-1,-1,-1):
#i 指向当前堆最后一个元素
li[0],li[i] = li[i],li[0]
sift(li,0,i-1)#i-1是新的hight
?
完整代码：
"""
CSDN : heart_6662
PYTHON amateur
"""
def sift(li,low,hight):
'''
li ； 列表
low ： 根节点的位置
hight : 堆最后一个元素的位置
return
'''
i = low
j = 2*i +1
tem = li[low] #记录堆顶
while j <= hight: #只要j位置有数
if j+1 <= hight and li[j+1] > li[j]: #如果右孩子大于左孩子
j = j + 1 #指向右孩子
if li[j] > tem:
li[i] = li[j]
i = j #往下看一层
j = 2 * i + 1
else: #tem更大，把tem放在i的位置上
li[i] = tem
break
else:
li[i] = tem
def heap_sort(li):
n = len(li)
#建堆
for i in range((n-2)//2,-1,-1):
#i表示建堆的时候调整部分的下标
sift(li,i,n-1)
#建堆完成
#将堆释放
for i in range(n-1,-1,-1):
#i 指向当前堆最后一个元素
li[0],li[i] = li[i],li[0]
sift(li,0,i-1)#i-1是新的hight
li = [i for i in range(100)]
import random
random.shuffle(li)
print(li)
heap_sort(li)
print(li)