难以理解堆排序（C++版）

堆排序C++版

• • 一、什么是堆排序？

  • • 1、什么是堆
    • 2、堆排序
    • 3、堆排序步骤

  • 二、堆排序的优缺点

  • 三、代码示例

一、什么是堆排序？

1、什么是堆

堆是一种特殊的二叉树类型，在结构上包含两个主要特征：其一是所有节点都至少与相应子树中的所有节点数值相等；其二是构成一个完美平衡结构，在最后一层的所有叶子都位于该层的最左端。

该数据结构包含两种类型的最大和最小结构，在最大结构中每个父节点都不低于其子节点，在最小结构中每个父节点都不高于其子节点

2、堆排序

该排序方法采用基于数据结构的"树"形组织形式来实现元素间的比较与交换操作，在每一轮选择中都能确定一个最终位置从而逐步完成整个序列的有序排列过程

3、堆排序步骤

以最大堆排序为例说明，在数据存储时采用数组形式存放的情况下，则首先会执行一轮循环操作：对所有节点逐一考察并建立一个以根节点为起点的最大堆结构；其中最大的根数据位于索引0的位置；随后进入排序阶段：基于构建的最大堆开始降序排列：从数组末尾向前逐个检查所有节点：每次检查时将当前最大的值放置于当前处理的位置上；直到所有项都被正确归位完成排序过程。（参考代码注释）

二、堆排序的优缺点

优点：
1）运行效率高；该算法的时间复杂度