当前位置:首页 » 《随便一记》 » 正文

堆排序详解_m0_57330725的博客

9 人参与  2022年04月15日 17:57  分类 : 《随便一记》  评论

点击全文阅读


我们学过很多排序,其实它们的很多效率其实不是很高,比如像冒泡排序之类的,接下来我们来介绍下什么是堆排序。

如果我们要排升序的话,我们要建大堆,说明如下:

 

 如图这是我们建好的大堆,但我们怎么去拍升序呢,不能重新开辟新的空间,我们是不是可以把80这一节点和最后这一节点换下。

 换完后,我们在可以向下调整,把53往下调,把比53大的往上调以此类推

 在把75和最后21换,最后排成了一个升序。代码如下

void AdjustUp(HPDtaType* a, int chlid)//向上调整
{
	int parent = 0;
	parent = (chlid - 1) / 2;
	while (chlid)//当chlid为零时,循环停止
	{
		if (a[parent] < a[chlid])//当孩子结点大于双亲结点时,就进行交换,
		{
			HPDtaType tmp = a[chlid];
			a[chlid] = a[parent];
			a[parent] = tmp;
			chlid = parent;
			parent = (chlid - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void Adjustdown(HPDtaType* a, int n, int partent)//向下调整
{
	int chlid = 0;
	chlid = partent * 2 + 1;
	while (chlid < n)
	{
		if (chlid + 1<n&&a[chlid + 1] > a[chlid])
		{
			chlid++;
		}
		if (a[chlid] > a[partent])
		{
			Swap(&a[chlid], &a[partent]);
			partent = chlid;
			chlid = partent*2+1;
		}
		else
		{
			break;
		}
	}
}
void Swap(HPDtaType*px, HPDtaType*py)//交换接口
{
	HPDtaType tmp = *px;
	*px = *py;
	*py = tmp;
}

以上使我们所要用到的接口函数

#include"HeapSort.h"
int main()
{
	int a[] = { 10, 12, 54, 33, 21, 60, 75, 70, 43, 53, 80 };
	int sz = sizeof(a) / sizeof(a[0]);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	for (int i = 1; i < sz; i++)
	{
		AdjustUp(a, i);//建大堆
	}
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	for (int end = sz - 1; end >= 0; end--)
	{
		Swap(&a[end], &a[0]);
		Adjustdown(a, end, 0);
	}
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

这是我们最后的测试函数

 这是我们最后的结果,得到了升序


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/38144.html

升序  这是  这一  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 微风知我意限免完整章节合集‌_沈梦肖宇轩宇轩反转剧情碎片化试读
  • 一见青山云端月结局+番外+续集(苏慕绾沈廷淮),一见青山云端月结局+番外+续集
  • 幻花情劫谢长憬流萤结局+番外榜单完本_完本幻花情劫谢长憬流萤结局+番外榜单
  • 我在回忆里万劫不复反转剧情全书秦见鹿谢梵声在线
  • 「她用母亲的救命钱养小白脸,我用她的命还债」完结版全文_[徐子轩江雪恩爱]命运转折章节速览
  • 流萤谢长憬(幻花情劫谢长憬流萤免费)结局_(流萤谢长憬幻花情劫谢长憬流萤免费全书结局)结局列表_笔趣阁(流萤谢长憬)
  • 完结文往梦难复温+后续+结局列表_完结文往梦难复温+后续+结局(沈淮霆宋思予)
  • 我在回忆里万劫不复完结爽文全面完结谢梵声秦见鹿完本_我在回忆里万劫不复完结爽文全面完结(谢梵声秦见鹿)
  • [小丑]后续已完结_[陆以祥姜薇秦婉]小说章节免费试读
  • 我在梦里等花开结局+番外免费(我在梦里等花开结局+番外陆子轩宋知禾)完结_(陆子轩宋知禾)列表_笔趣阁(我在梦里等花开结局+番外)
  • (番外)+(结局)我在梦里等花开结局+番外(陆子轩宋知禾)全书在线_(我在梦里等花开结局+番外)列表_笔趣阁(陆子轩宋知禾)
  • 沈廷淮苏慕绾(一见青山云端月)_(沈廷淮苏慕绾)列表_笔趣阁(一见青山云端月)

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1