Question

堆排序是选择排序吗

Answer 1

堆排序是一种树形选择排序，堆排序实质上也是选择排序，但不使用遍历的方式查找待排序区间最大数，而是通过堆来选择待排序区间最大数。当排升序时要建大堆，排降序要建小堆。

选择排序是不稳定的排序，相同数据无法保证排序前后位置不变。因为待排序区间最小值或最大值都是要比较完一整轮才能得出结果，所以无论好坏都是比较n次，再算上整个序列遍历的O(n)，最后时间复杂度就为O(n^2)。

堆排序的树形选择排序规则

（1）满足前者是小根堆，满足后者是大根堆。

（2）假设将此序列对应的一维数组当成一棵完全二叉树，则小根堆满足以下性质：树中任一非叶子的关键字均不大于其左右孩子结点的关键字。

（3）假设将此序列对应的一维数组当成一棵完全二叉树，则大根堆满足以下性质：树中任一非叶子的关键字均不小于其左右孩子结点的关键字。

以上内容参考  百度百科-堆排序