【数据结构】-排序-堆排序_手推堆排序

作者：爱喝兽奶帝天荒 | 2024-07-29 21:55:48

踩

手推堆排序

堆排序是选择排序中的一种，选择排序的思想是在未排序的数列中选择一个最大或者最小的数据加入已排序序列，大根堆这个结构的根节点就是最大值，因此会大大方便选择。

在完全二叉树中，根>左，右

手动建堆：

第一步：顺序建立一棵树

第二步：检查非叶子结点是否满足根>左，右，不满足就将当前节点与最大的一个孩子互换（0位置不存储），注意调整上层结点的时候有可能破坏下层的堆结构，此时要继续检查。不断下坠，下坠到无法下坠为止。

算法建堆：

1.从n/2位置开始，逐个非终端节点都要调用AdjustHeap,因为n/2是第一个非叶子节点的序号，所有的叶子节点都已经满足堆的定义了，所以所有的叶子节点都不需要调整。

2.if语句中的条件不能随便安排顺序 if(i<n&&a[i] < a[i + 1]) 如果把这两个条件交换顺序会造成数组越界，也就是说if语句中的条件判断是从左到右顺序执行的。


//调整堆
void adjust

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/900789