😎博客昵称：博客小梦
😊最喜欢的座右铭：全神贯注的上吧！！！
😊作者简介：一名热爱C/C++，算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主！
😘博主小留言：哈喽！😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不多说，文章推上！欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘
前言🙌
哈喽各位友友们😊，我今天又学到了很多有趣的知识，现在迫不及待的想和大家分享一下！😘我仅已此文，手把手带领大家追梦之旅【数据结构篇】——看看小白试如何利用C语言“痛”撕堆排序~ 都是精华内容，可不要错过哟！！！😍😍😍
堆的应用 —— 堆排序算法：
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
1.建堆
升序：建大堆
降序：建小堆
2.利用堆删除思想来进行排序建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
- 利用向上调整建堆的时间复杂度：O(n*logn);
- 利用向下调整建堆的时间复杂度：O(n);
因此，在堆排序中应用向下调整算法要优于向上调整算法。所有结点的排序调整部分也是O(n*logn).
最优的堆排序为： O(n + n*logn)。
堆排序算法源代码分享
#include<stdio.h> void Swap(int* p1, int* p2) { int tem = *p1; *p1 = *p2; *p2 = tem; } //建小堆 //void AdjustDown(int* a, int size, int parent) //{ // int child = parent * 2 + 1; // while (child < size) // { // if (child + 1 < size && a[child + 1] < a[child]) // { // child++; // } // // if (a[child] < a[parent]) // { // Swap(&(a[parent]), &(a[child])); // parent = child; // child = parent * 2 + 1; // } // else // { // break; // } // } //} //建大堆 void AdjustDown(int* a, int size, int parent) { int child = parent * 2 + 1; while (child < size) { if (child + 1 < size && a[child + 1] > a[child]) { child++; } if (a[child] > a[parent]) { Swap(&(a[parent]), &(a[child])); parent = child; child = parent * 2 + 1; } else { break; } } } void HeapSort(int* a, int size) { //排降序 -- 建小堆 /*for (int i = (size - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, size, i); }*/ //排升序 -- 建大堆 for (int i = (size - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, size, i); } //排序 int end = size - 1; while (end > 0) { Swap(&(a[0]), &(a[end])); AdjustDown(a, end, 0); end--; } } int main() { int a[6] = { 22,33,222,1,2,55 }; HeapSort(a, 6); for (int i = 0; i < 6; i++) { printf("%d ", a[i]); } printf("\n"); return 0; }
运行结果测试截图：
总结撒花💞
本篇文章旨在分享详解小白如何使用C语言实现堆数据结构。希望大家通过阅读此文有所收获！
😘如果我写的有什么不好之处，请在文章下方给出你宝贵的意见😊。如果觉得我写的好的话请点个赞赞和关注哦~😘😘😘
