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

堆排序详解_m0_57330725的博客

8 人参与  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://zhangshiyu.com/post/38144.html

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

  • 评论(0)
  • 赞助本站

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

最新文章

  • 大雁南飞人不归结局+番外(沈砚之姜曼殊)结局_(大雁南飞人不归结局+番外大雁南飞人不归结局+番外全书结局)结局列表_笔趣阁(沈砚之姜曼殊)
  • 夕拾难觅朝阳苏亦葵厉晏行完本_夕拾难觅朝阳(苏亦葵厉晏行)
  • [老婆豪掷五百万给初恋,重生后我拒当提款机]人气小说未删减节选_唐欣顾承泽萧然小说节选推荐
  • 半堂花夜渡空城免费在线(裴砚泽沈诺柠)_半堂花夜渡空城免费在线
  • 大雁南飞人不归结局+番外优质全章(姜曼殊沈砚之)_大雁南飞人不归结局+番外优质全章姜曼殊沈砚之
  • [绿茶室友邀请我参加祭祖仪式,却不知我是老祖]人物羁绊章节精选_李岚老祖宗苏婧节选免费试读
  • (番外)+(全书)兰因絮果,爱恨全如玉碎+后续+结局(长乐肖风行)全书在线_兰因絮果,爱恨全如玉碎+后续+结局免费列表_笔趣阁(长乐肖风行)
  • 完结文被绿茶养女夺走真千金身份后,我杀疯了列表_完结文被绿茶养女夺走真千金身份后,我杀疯了(苏楠苏意安+)
  • 刹那芳华顾,褚墨景迟文月+番外+后续_刹那芳华顾,褚墨景迟文月+番外+后续列表
  • 被瘾症折磨的可怜校花免费结局+后续(张团团仁川)全书免费_(张团团仁川)被瘾症折磨的可怜校花免费结局+后续后续(张团团仁川)
  • [竹马率十万铁骑娶我,只为给心上人做嫁衣]反转剧情试读片段_尚书府限免完整章节合集‌
  • 方沐筱宋安(重生后,我将兼挑两房的老公一锅端+后续+结局)结局_(方沐筱宋安重生后,我将兼挑两房的老公一锅端+后续+结局全书结局)结局列表_笔趣阁(方沐筱宋安)

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

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