Java版八大排序之堆排序

悠悠 2023-02-10 05:13 7阅读 0赞

**堆排序**：是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

*  每个结点的值都大于或等于其左右孩子结点的值，**称为大顶堆**；
 *  每个结点的值都小于或等于其左右孩子结点的值，**称为小顶堆**。

时间复杂度：O (nlgn)

**堆排序的工作原理**：

*  假设序列有n个元素,先将这n建成大顶堆
 *  然后取堆顶元素，与序列第n个元素交换
 *  然后调整前n-1元素，使其重新成为堆
 *  然后再取堆顶元素，与第n-1个元素交换
 *  再调整前n-2个元素…直至整个序列有序。

介绍的是大顶堆的工作原理，下图给出小顶堆的图解，大顶堆与其类似，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQxOTIwMDY1_size_16_color_FFFFFF_t_70]新建结点用树结构与队列实现  
每一个结点有一个值，两个孩子，一个父节点的指向  
（小顶堆）构建树的时候用队列来构建，如果在队列中拿出结点来发现孩子结点比父节点小，那么把孩子结点和父节点的值交换，构建完成之后把堆顶元素拿出，把最后一行的最后一个元素放到堆顶，同时检查整个树的结构，调整成堆顶最小，继续拿出，如此循环往复

数组实现  
1.思路：  
把所有数组存到数组里，下标为n的结点，左孩子的下标为2n+1,右孩子的下标为2n+2，父亲的下标为（n-1）/2.定义一个游标指向最后一个元素，每拿出一个元素游标向前移一位。每次验证的时候如果不满足条件就把元素和其父亲的值互换，当所有的元素都满足小顶堆或者大顶堆的条件之后就把堆顶元素取出，然后把最后一个元素替换过来。如此循环

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQxOTIwMDY1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200520114907525.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQxOTIwMDY1,size_16,color_FFFFFF,t_70