数据结构排序算法之堆排序
博客专区 > htq 的博客 > 博客详情
数据结构排序算法之堆排序
htq 发表于1年前
数据结构排序算法之堆排序
  • 发表于 1年前
  • 阅读 0
  • 收藏 0
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

关于堆排序的相关知识非常复杂,不懂得可以参考任意一本数据结构教程,本博客只对堆排序框架及代码进行讲解。

堆排序分三个大的步骤:建初堆,堆调整,堆排序(其中最核心的是堆调整)
1建初堆:从数组中的最后一个非叶子节点开始,从下而上倒推(重复调用堆调整函数)
2堆调整:堆调整的前提是已建好了一个堆,但是因为输出,导致需要重新调整堆
3堆排序:从数组中所有元素开始,将堆顶元素与堆尾元素交换,然后数组的元素个数减一,然后继续调用堆调整函数。

基于以上框架,堆排序的代码如下:

#include<iostream>
using namespace std;
void sift(int a[],int root,int len)//堆调整函数
{
	int child=2*root;
	while(child<=len)//注意该函数的参数是从root到len,所以此处必须写=
	{
		if(child<len&&a[child]<a[child+1])//注意此处必须是child<len,之所以不取=因为child=child+1会溢出
		{
			child=child+1;
		}
		if(a[root]<a[child])
		{
			swap(a[root],a[child]);
			root=child;
			child=2*root;
		}
		else
		{
			break;//这个地方之所以可以直接break是因为堆调整函数的前提它本身就是堆,只不过交换了之后得重新调整,所以如果当前结点不满足,则它的子孙结点一定都不满足。
		}
	}
}
void cre_heap(int a[],int n)
{
	for(int i=n/2;i>=1;i--)//从最后一个非叶子结点开始,自底向上倒推,之所以是从非叶子结点开始。是因为该函数是将当前结点与其子结点比较大小,而叶子结点无子结点
	{
		
		sift(a,i,n);//调整堆函数的参数为,array_name,root,len.
	}
}
void heap_sort(int a[],int n)
{
	cre_heap(a,n);//堆排序的第一步,建初堆
	for(int i=n;i>=1;i--)
	{
		swap(a[1],a[i]);
		sift(a,1,i-1);
	}
}
void main()
{
	int a[10]={0,4,2,1,3,7,6,5,9,8};
	heap_sort(a,9);
	for(int i=0;i<10;i++)
	{
		cout<<a[i]<<' ';
	}
	cout<<endl;
}
程序运行结果如下:



共有 人打赏支持
htq
粉丝 17
博文 67
码字总数 1007
作品 3
×
htq
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: