堆排序+代码实现

**堆排序** 堆,heap,是二叉树的一种。小根堆有这样的性质——任意一个结点的值比它的左右孩子都要小。 ##排序思想 将待排元素看作是完全二叉树，物理上用一维数组存储。 **实现堆排序需要解决两个问题：** 1.如何将杂乱的完全二叉树初始化为一个堆？ 答：从最后一个非叶结点起，将该节点当做根，自上而下进行调整，使之成为一个堆。然后依次对倒数第二个、倒数第三个、直至正数第一个结点进行此操作。 2.输出堆顶元素后，如何将余下的元素调整为一个堆？ 答：将最后一个结点放在原根结点位置上，以它为根进行上述的调整。 ##复杂度分析。 二叉树的层数计算方法，从上往下，1,2,3,4...... 耗时的操作有构造初始堆和调整堆两部分。 对深度为h的堆进行自上而下的调整，最多比较次数为2*(h-1)。 在初始化堆的过程中，完全二叉树的高度为h，总的比较次数为  综上，堆排序在复杂度最坏的情况下为O((1)式+(2)式)=O(n*logn)。 ##代码 初始序列为`1 8 6 2 5 4 7 3`一组数采用堆排序，当建堆（小根堆）完毕时，堆所对应的二叉树中序遍历序列为：A A.8 3 2 5 1 6 4 7  B.3 2 8 5 1 4 6 7  C.3 8 2 5 1 6 7 4  D.8 2 3 5 1 4 7 6