堆排序

堆排序

堆排序的核心思想：借助堆数据结构，不断输出当前堆顶元素，每次堆顶离开当前堆后，对剩余元素重新调整成堆，直到堆中只剩下一个元素；元素的输出序列可转换成元素的有序序列

思路：

1、 我们以最大堆为例，在原数组上把元素按从小到大排序

2、 我们先对无序的数组初始化；即调整成最大堆；

2.1、无序的数组初始化最大堆思路：假设堆从root到叶子下标从0开始，它有一个性质：即int i = （叶子的节点下标/2) 得到第一个子树，我们把它向下调整成最大堆，然后i--,把以i为下标的子树调整成最大堆…直到root

3、交换arr[0]和arr[length - 1] , 把剩余的元素调整成最大堆

4、(length-1)-- ; 循环调用步骤3-4，直到还剩下一个元素

向下调整思路：

1、 以下图为例，index = 0(要调整的元素) ,我们先确定它是否有左孩子，有左孩子则继续；否则退出

2、 我们把要调整的元素和两个孩子中最大的那个比较，如果要调整的元素值大，则返回；否则交换要调整的元素和子孩子中大的那一个，更新index；循环调用1-2

请看图

好了，知道了思路我们来实现一下

向下调整

注：

1、因为堆的结构是完全二叉树，因此可以用数组的结构来存储(看图)

2、初始化数组时，为什么不直接从root开始?

因为我们不能保证root的左右两个子树满足最大堆结构，堆排序的前提：堆结构中，只有要调整的那个元素，不满足最大堆结构

3、 为什么向下调整用while循环，因为我们也不知道循环多少次

4、 swap函数是c++自带的

关注奇迹码农

获取更多编程干货