排序-堆排序(Heap Sort)-北京尧图网络

目录前言堆排序思路为什么升序 → 建大根堆降序 → 建小根堆。演示图如下代码如下练习排序的时间复杂度与空间复杂度结语前言排序算法是计算机数据处理领域最基础、最核心的一类算法广泛应用于数据检索、业务统计、任务调度等场景。常见的排序算法中冒泡排序、选择排序、插入排序时间复杂度为(O(n^2))面对大规模数据时效率低下快速排序虽平均性能优异但最坏情况下时间复杂度会退化至 (O(n^2))且属于不稳定排序。堆排序作为一种基于二叉堆数据结构实现的原地排序算法凭借稳定的 (O(nlog n)) 时间复杂度、(O(1)) 的额外空间开销弥补了上述算法的短板。它借助大根堆、小根堆的特性不断选取当前区间内的极值逐步完成元素就位。在学习堆排序的过程中非常容易出现「升序建小根堆」的直觉误区。本文从堆的底层性质出发完整讲解堆排序的原理、向上调整、向下调整、建堆逻辑与排序流程结合实例剖析升序选择大根堆、降序选择小根堆的根本原因给出可运行的 C 代码实现帮助彻底吃透堆排序。其他排序快速排序排序-快速排序Quick sort基础版-CSDN博客插入排序排序—插入排序(Insertion Sort)-CSDN博客冒泡排序与选择排序排序-选择排序Selection Sort冒泡排序Bubble Sort-CSDN博客希尔排序排序-希尔排序(Shell Sort)-CSDN博客归并排序排序-归并排序Merge Sort-CSDN博客堆排序思路堆排序利用大根堆的性质堆顶元素永远是当前数组里最大值。先把整个数组构建成大根堆。堆顶最大值和数组最后一个元素交换最大值就位。剩下前面未排序部分重新向下调整恢复成大根堆。重复交换调整直到全部有序最终数组升序。重点升序 → 建大根堆降序 → 建小根堆。虽然这个堆是完全二叉树但是本质是还是数组这是我们将其看成了堆。为什么升序 → 建大根堆降序 → 建小根堆。堆排序是原地排序算法不开额外数组直接在原数组上完成排序。核心循环逻辑固定不变将数组构建成堆。交换堆顶元素和当前堆区间最后一个元素。缩小堆的范围末尾元素已经排好不再参与堆调整。对新堆顶执行向下调整恢复堆结构重复直到有序。最核心的一步堆顶元素不是直接输出拿走而是被交换到数组尾部。这就是口诀的根源升序如果错误使用小根堆会发生什么如果你升序强行建小根堆。小根堆堆顶是当前最小值。第一次交换最小值放到数组末尾。演示图如下代码如下升序堆排序#includeiostream using namespace std; void AdjustUp(int* a, int child) { int parent (child - 1) / 2; while (child 0) { if (a[parent] a[child]) { swap(a[parent], a[child]); child parent; parent (child - 1) / 2; } else { break; } } } void AdjustDown(int* a, int n, int parent) { int child parent * 2 1; while (child n) { if (a[child] a[child 1] child 1 n)child; if (a[child] a[parent]) { swap(a[parent], a[child]); parent child; child parent * 2 1; } else { break; } } } //升序的堆排序 void HeapSort(int* a, int n) { for (int i 1; i n; i) AdjustUp(a, i); int end n - 1; while (end 0) { swap(a[0], a[end]); AdjustDown(a, end, 0); --end; } } int main() { int a[] { 10,9,8,7,6,5,4,3,2,1 }; HeapSort(a, 10); /*SelectionSort(a, 10);*/ //InsertionSort(a, 3); //MergeSort(a, 10); /*ShellSort(a, 10);*/ /*MergeSort(a, 10);*/ /*QuickSortNonR(a, 0,9);*/ for (auto e : a) { cout e ; } return 0; }练习自己完成降序的堆排序排序的时间复杂度与空间复杂度结语希望可以帮助到你谢谢观看

排序-堆排序(Heap Sort)

相关推荐

AI大模型与数学第62课：向量内积、范数、夹角

FPGA与ADC/DAC系统设计：从原理到实战的硬件开发指南

HarmonyOS 7.0 / API 26 多窗口输入焦点治理：鸿蒙电脑和平板为什么会抢输入框

更多资讯

井冈山电工证报名中心内部消息：学历不高也能拿证，收入翻倍不是梦

山东建筑特种工证查询怎么报名才能避免过期

成都建筑电工证咋考？学历不高怕报不上名？看懂含金量再决定

证书过期了不知道怎么复审延期？佛山高压电工证报名费值不值得考

特种工信号工培训多少钱？学历不高也能报上名！

工地太忙根本没时间复习考试？电工证考试科目3技巧+上岗必备全攻略

今日更新

金坛办电工证在哪里？考前押题能帮你少走弯路

怎样查看真假电工证怎么考

史密斯内部电工证值不值得考？怕考不过白交培训费的看过来

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？