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