目录Python全系列 教程
3567个小节阅读：5931k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本，未来主流的版本
人工智能 教程
顺势而为，AI创新未来
大厂算法 教程
算法，程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
堆排序(heap sort)是一种基于堆数据结构实现的高效排序算法。我们可以利用已经学过的“建堆操作”和“元素出堆操作”实现堆排序
输入数组并建立最大堆
将堆顶元素(第1个元素)和堆底元素(最后1个元素)交换。完成交换后，堆的长度减1，已排序的元素数量为1
重新维护堆特性(down操作)
循环执行第2与3步。循环$n-1$轮后，完成数组排序
xxxxxxxxxxclass MyHeap: def __init__(self,heap:list[int]): self.heap = heap self.init_data() def size(self): return len(self.heap)
def init_data(self): '''维护特性''' for i in range(self.size()//2-1,-1,-1): self.down(i,self.size()) def down(self,index:int,size): # 默认认为index是最大值 max_index = index # 获取左右子节点 left = index*2+1 right = index*2+2 # 判断哪个索引上的数字最大 if left < size and self.heap[left] > self.heap[max_index]: max_index = left if right < size and self.heap[right] > self.heap[max_index]: max_index = right # 如果max_index的值不再是Index,说明需要交换 if max_index != index: self.heap[max_index],self.heap[index] = self.heap[index],self.heap[max_index] # 递归调用 self.down(max_index,size)
def heap_sort(self): '''堆排序''' for i in range(self.size()-1): self.heap[0],self.heap[-1-i] = self.heap[-1-i],self.heap[0] self.down(0,self.size()-1-i) return self.heap
if __name__ =='__main__': data = [8,1,7,2,6,3] heap = MyHeap(data) print(heap.heap) heap.heap_sort() print(heap.heap)时间复杂度为 $ O(n \log n) $、非自适应排序：建堆操作使用 $ O(n) $ 时间。从堆中提取最大元素的时间复杂度为 $ O(\log n) $ ，共循环 $ n-1 $ 轮。
空间复杂度为 $O(1)$、原地排序：几个指针变量使用 $ O(1) $ 空间。元素交换和堆化操作都是在原数组上进行的。
非稳定排序：在交换堆顶元素和堆底元素时，相等元素的相对位置可能发生变化
实时效果反馈
1. 关于堆排序算法，说法错误的是？
A 堆排序需要移除顶元素、维护堆反复操作
B 堆排序目的就是维护堆特性
C down操作就是把数据往下移动
D 堆排序可以最大堆也可以是最小堆
答案
1=>B