堆排序属于选择排序吗
发布网友
发布时间：2022-10-13 12:31
共1个回答
热心网友
时间：2023-11-04 04:59
堆排序是一种树形选择排序，堆排序实质上也是选择排序，但不使用遍历的方式查找待排序区间最大数，而是通过堆来选择待排序区间最大数。当排升序时要建大堆，排降序要建小堆。
选择排序是不稳定的排序，相同数据无法保证排序前后位置不变。因为待排序区间最小值或最大值都是要比较完一整轮才能得出结果，所以无论好坏都是比较n次，再算上整个序列遍历的O(n)，最后时间复杂度就为O(n^2)。
堆排序的树形选择排序规则
（1）满足前者是小根堆，满足后者是大根堆。
（2）假设将此序列对应的一维数组当成一棵完全二叉树，则小根堆满足以下性质：树中任一非叶子的关键字均不大于其左右孩子结点的关键字。
（3）假设将此序列对应的一维数组当成一棵完全二叉树，则大根堆满足以下性质：树中任一非叶子的关键字均不小于其左右孩子结点的关键字。
以上内容参考 百度百科-堆排序
