swust.oj1015: 堆排序算法

1015: 堆排序算法 题目描述

编写程序堆排序算法。按照从小到大的顺序进行排序，测试数据为整数。 输入

第一行是待排序数据元素的个数； 第二行是待排序的数据元素。（提示：用小根堆）

输出

一趟堆排序的结果。

样例输入

10 50 36 41 19 23 4 20 18 12 22

样例输出

4 12 20 18 22 41 50 36 19 23

#include<stdio.h>

void swap(int a[],int max,int i)
{
          
   
	int temp=a[i];
	a[i]=a[max];
	a[max]=temp;
}

void heapify(int tree[],int n,int i)
{
          
   
	//参数为数组tree，数组长度n,i是当前子树的根节点 
	if(i>=n)	return;//递归出口 
	int lc=2*i+1;
	int rc=2*i+2;
	int min=i;
	//找到当前节点左右子树的最大值并与当前节点交换 
	if(lc<n&&tree[lc]<tree[min])
	{
          
   
		min=lc;
	}
	if(rc<n&&tree[rc]<tree[min])
	{
          
   
		min=rc;
	}
	if(min!=i)
	{
          
   
		swap(tree,min,i);
		heapify(tree,n,min);//对被交换的子树进行排序 
	}
 } 

void build_heap(int tree[],int n)
{
          
   
	//从最后一个节点的父节点开始创建最大堆，直到遇到根节点 
	int last_node=n-1;
	int parent=(last_node-1)/2;//最后一个节点的父节点 
	for(int i=parent;i>=0;i--)
	{
          
   
		heapify(tree,n,i);
	}
}

void heap_sort(int tree[],int n)
{
          
   
	//先构建一个最大堆 
	build_heap(tree,n);
	int i;
	//最后一个节点和根节点交换，并将最后一个节点砍掉 
	for(int i=n-1;i>=0;i--)
	{
          
   
		swap(tree,i,0);
		heapify(tree,i,0);//i表示当前树的节点 
	}
}
int main()
{
          
   
	int n;
	scanf("%d",&n);
	int tree[n];
	for(int i=0;i<n;i++)
	{
          
   
		scanf("%d",&tree[i]);
	 } 
	build_heap(tree,n);
	for(int i=0;i<n;i++)
	{
          
   
		printf("%d ",tree[i]);
	}
}

b站大佬讲解视频

https://www.bilibili.com/video/BV1Eb41147dK?from=search&seid=7761090493431357921