一:定义
堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆排序是一种树形选择排序,在排序过程中可以把元素看成是一颗完全二叉树,每个节点都大(小)于它的两个子节点,当每个节点都大于等于它的两个子节点时,就称为大顶堆,也叫堆有序; 当每个节点都小于等于它的两个子节点时,就称为小顶堆。
下面是我们要保存在数组中的堆的形式
二:堆排序算法
1.将长度为n的待排序的数组进行堆有序化构造成一个大顶堆
2.将根节点与尾节点交换并输出此时的尾节点
3.将剩余的n -1个节点重新进行堆有序化
4.重复步骤2,步骤3直至构造成一个有序序列
三:如何构造堆(大顶堆)
例:{5, 2, 6, 0, 3, 9, 1, 7, 4, 8}
第一次找到[n/2]处,进行构造:
我们比较父节点,左右孩子结点的大小,将最大的作为堆顶
第二次,我们对上次找到位置-1即可,找到结点0,对其左右孩子比较,构造这三个结点的最大堆
第三次,我们找到结点6,要对其进行构造,结果如下
第四次(重点),我们不止要构造双亲和左右孩子,我们还要比较其孩子结点为根的堆是否正确,不然我们需要进行调整
我们发现将8,7,2三个结点变为了最大堆,但是其中2,3子树不再是一个最大堆,我们需要对其修改
第五次:选取结点9进行构造
发现以结点5为根的子树不是最大堆,我们需要进行调整
完成构建:
四:堆排序(堆存储在数组中)
第一步:将最大值和最后的一个元素交换
第二步:将剩余的结点再次进行堆构造
第三步:参照第一步
按照上面循环,最终结果为
五:性能分析
运行时间主要消耗在构造堆和重建堆时的反复筛选上。
构造堆的时间复杂度为O(n)
重建堆时时间复杂度为O(nlogn)。
所以总体就是O(nlogn)。
不适合排序序列个数较少的情况
转载于:https://my.oschina.net/u/4167465/blog/3077654
分享到:
相关推荐
- **排序方式**:MySQL主要有三种排序实现:常规排序、优化排序和优先队列排序,涉及快速排序、归并排序和堆排序。 - **常规排序流程**: - (1) 读取满足`WHERE`条件的记录。 - (2) 将记录的主键和排序键存储到`...
尽管如此,插入排序的时间复杂度在最坏情况下仍然是O(n^2),这意味着对于已经部分排序或者完全无序的数据,它的性能可能不如其他高级排序算法,如快速排序、归并排序或堆排序。 在实际应用中,选择哪种排序算法取决...
- **堆排序**:利用堆这种数据结构进行排序,可以实现原地排序且时间复杂度较低。 - **归并排序**:使用分治策略,将大问题分解成小问题解决,再合并结果。 每种排序算法都有其特点,适用于不同的场景。例如,冒泡...
JavaScript实现的八大排序算法包括:直接插入排序、希尔排序、简单选择排序、堆排序、冒泡排序、快速排序、归并排序和基数排序。这些算法都是内部排序,也就是说,数据记录在内存中进行排序,不需要访问外部存储。 ...
使用快速排序、归并排序或堆排序代替插入排序或冒泡排序。 - **数据结构的选择**:根据程序需求选择合适的数据结构,如使用链表处理大量插入和删除操作。 #### 三、其他注意事项 - **循环优化**:减少循环中的计算...
数据结构还涉及查找和排序技术,如二分查找、哈希查找和各种排序算法(如冒泡排序、快速排序、归并排序等)。这些技术在日常编程中广泛使用,优化了数据处理的效率。 在中职计算机教学中,教师应当将数据结构的理论...
在实际应用中,我们往往会选择更高效的排序算法,如快速排序、归并排序或堆排序,但了解这些基本算法有助于我们更好地理解和优化高级算法。同时,学习和实践这些算法也是提升编程能力的重要步骤。
树型结构是数据组织的重要方式,论文可能涉及二叉树、平衡树(如AVL树、红黑树)以及堆(最大堆、最小堆)。树的遍历(前序、中序、后序)和操作(插入、删除、查找)也是重点内容。 二分算法是高效处理有序数据的...
链表可以用于解决各种问题,如约瑟夫问题(Josephus Problem)、排序算法(如链表排序)、搜索问题(链表中查找特定元素),以及更复杂的数据结构如广义表。在PHP的底层实现,由于其基于C语言,内存管理遵循栈区、堆...
2. 堆内存:用于存储数组对象本身和新创建的对象,由垃圾回收器管理,自动清理不再使用的对象。 三、数组的使用方法 1. 获取数组元素:通过数组名[下标]来获取特定位置的元素,例如arr[3]。 2. 获取数组长度:使用...
与JOIN不同,它们不需要共享的关联字段,而是简单地将结果集堆叠在一起。 例如,假设我们有两个表,`user`表存储用户基本信息,而`user_history`表记录用户的活动历史。如果我们想找出所有名字以“王”开头的用户,...
侯克林老师作为一位资深的C++教育者,他的课程资料深入浅出,深受学习者喜爱。这次分享的“houkelin 老师课件”正是他教学经验的结晶,包含了STL(标准模板库)、指针操作以及内存管理等核心知识点。 首先,我们来...
### 第一讲:浅谈国内笔试面试风格及准备方法 1. **实现一个Memcpy函数** - `memcpy`函数用于在内存区域之间复制固定数量的字节。 - 实现时需注意处理边界情况和防止缓冲区溢出等问题。 2. **STL中vector的实现...