追梦之旅【数据结构篇】——看看小白试如何利用C语言“痛”撕堆排序
😎博客昵称：博客小梦
😊最喜欢的座右铭：全神贯注的上吧！！！
😊作者简介：一名热爱C/C++，算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主！
😘博主小留言：哈喽！😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不多说，文章推上！欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘
前言🙌
哈喽各位友友们😊，我今天又学到了很多有趣的知识，现在迫不及待的想和大家分享一下！😘我仅已此文，手把手带领大家追梦之旅【数据结构篇】——看看小白试如何利用C语言“痛”撕堆排序~ 都是精华内容，可不要错过哟！！！😍😍😍
堆的应用 —— 堆排序算法：
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
- 建堆
升序：建大堆
降序：建小堆 - 利用堆删除思想来进行排序建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
- 利用向上调整建堆的时间复杂度：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语言实现堆数据结构。希望大家通过阅读此文有所收获！
😘如果我写的有什么不好之处，请在文章下方给出你宝贵的意见😊。如果觉得我写的好的话请点个赞赞和关注哦~😘😘😘
