带你读《图解算法小抄》十四、排序（14）

带你读《图解算法小抄》十四、排序（13）https://developer.aliyun.com/article/1348137?groupCode=tech_library

3）基本思想

• 将待排序序列构造成一个大顶堆
  

注意：这里使用的是数组，而不是一颗二叉树

• 此时：整个序列的 最大值就是堆顶的根节点
  
• 将其 与末尾元素进行交换，此时末尾就是最大值
  
• 然后将剩余 n-1 个元素重新构造成一个堆，这样 就会得到 n 个元素的次小值。如此反复，便能的得到一个有序序列。
  

4）堆排序步骤图解

对数组 4,6,8,5,9 进行堆排序，将数组升序排序。

步骤一：构造初始堆

1. 给定无序序列结构 如下：注意这里的操作用数组，树结构只是参考理解
   

将给定无序序列构造成一个大顶堆。

b）此时从最后一个非叶子节点开始调整，从左到右，从上到下进行调整。

叶节点不用调整，第一个非叶子节点 arr.length/2-1 = 5/2-1 = 1 ，也就是 元素为 6 的节点。

比较时：先让 5 与 9 比较，得到最大的那个，再和 6 比较，发现 9 大于 6，则调整他们的位置。

c）找到第二个非叶子节点 4，由于 [4,9,8] 中，9 元素最大，则 4 和 9 进行交换

带你读《图解算法小抄》十四、排序（15）https://developer.aliyun.com/article/1348135?groupCode=tech_library