介绍
为了能更好的理解堆排序
,前两篇"插播"了它的相关知识(二叉树、堆)。特别了解了堆
的相关概念以后就很好理解堆排序
了。堆排序的逻辑:
1.将待排序数数组映射为完全二叉树
(忘了的同学请看二叉树的介绍);
2.将完全二叉树转换为小根堆(升序时需要)或者大根堆(降序需要);
3.不断的弹出根
(即pop
操作,忘了的同学请看堆),存放到一个已排序数组直到堆
为空树
。
例子
以老数组[77, 6, 37, 96, 34, 6, 14]
为例。
先建立小根堆:
(还没写完,这两天实在是时间紧,改天补上!)
时间复杂度
感谢阅读!欢迎关注!持续更新中...