追梦之旅【数据结构篇】——看看小白试如何利用C语言“痛”撕堆排序

   
😎博客昵称：博客小梦
😊最喜欢的座右铭：全神贯注的上吧！！！
😊作者简介：一名热爱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语言实现堆数据结构。希望大家通过阅读此文有所收获！
   😘如果我写的有什么不好之处，请在文章下方给出你宝贵的意见😊。如果觉得我写的好的话请点个赞赞和关注哦~😘😘😘