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