def sift(nums, low, high):
# 构造大根堆（假设左右子树已是大根堆）。
# 索引由0开始。
# 递归版本，空间复杂度不为O(1)
# left, right = 2*low+1, 2*low+2
# large_index = low
# if left<=high and nums[low]<nums[left]:
# large_index = left
# if right<=high and nums[left]<nums[right]:
# large_index = right
# if large_index != low:
# nums[low], nums[large_index] = nums[large_index], nums[low]
# sift(nums, large_index, high)
# 非递归版本，空间复杂度O(1)
i, j = low, low*2+1 # R[j]是R[i]的左孩子
tmp = nums[i] # tmp保存根节点的值
while j <= high:
if j < high and nums[j] < nums[j+1]:
j += 1
if tmp < nums[j]:
nums[i] = nums[j]
i = j
j = 2*i+1
else:
break
nums[i] = tmp
def HeapSort(nums):
low, high = 0, len(nums)-1
i = len(nums)//2-1 # 最大非叶节点索引（索引由0开始）
while i >= 0:
sift(nums, i, high)
i -= 1
for i in range(high, 0, -1):
nums[0], nums[i] = nums[i], nums[0]
sift(nums, 0, i-1)
return nums
inputs = [1, 2, 34, 35, 23, 56, 2, 13]
print(HeapSort(inputs)) # [1, 2, 2, 13, 23, 34, 35, 56]
Python堆排序
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 堆基本概念 堆排序是一个很重要的排序算法，它是高效率的排序算法，复杂度是O(nlogn)，堆排序不仅是面试进场考的...
- 最近在复习经典排序算法，自己用python也实现了一下，这里不会涉及到原理（因为网上方法已经很详细啦），就把函数贴...
