堆排序思路讲解

r囧r小猫 2023-07-01 13:55 10阅读 0赞

农历腊月二十八，快过年喽，咱们来聊聊**堆排序**吧。  
**堆**的**物理存储结构**是一维数组，**逻辑存储结构**是完全二叉树。  
**堆**是一棵**无序树**。  
**堆排序**是利用了**堆**这个**数据结构**而设计的一种排序算法，是一种选择排序，最好，最坏，平均时间复杂度都是 O(nlogn)，是**不稳定的排序**。  
（不稳定的排序是指 如果有两个相同的数字，在排序之后位置发生了变化，即为不稳定的排序）  
下面是**堆的结构**：  
大顶堆和小顶堆  
**大顶堆**：每个结点的值都大于或等于其左右孩子结点的值。  
**小顶堆**：每个结点的值都小于或等于其左右孩子结点的值。  
如图：  
![四年哦我RPG皮][RPG]  
构建完堆结构之后，剩下的就是**堆排序的思想**了。  
我以大顶堆为例。  
每次将堆顶的元素和树中最后一个叶子节点交换，然后就取得了这个树中的最大值，再将这个交换后的树，再次按照构建大顶堆的方法，再次调整，使其满足最大值在堆顶，再次执行交换，直到将所有节点都取出得到，排列出一个降序的组合就完成了。  
放个图吧，多看几遍一定能看懂。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZyaXN0amNqZG5jZw_size_16_color_FFFFFF_t_70]  
如果有不对的地方，还请多指教呀，大家一起进步呀！

[RPG]: https://img-blog.csdnimg.cn/20200122161018200.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZyaXN0amNqZG5jZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZyaXN0amNqZG5jZw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200122161943619.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZyaXN0amNqZG5jZw==,size_16,color_FFFFFF,t_70