【C语言数据结构】堆排序讲解

?一.代码部分：

//堆排序
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void swap(int* a,int* b)//用于换位
{
	int tamp;
	tamp=*a;
	*a=*b;
	*b=tamp;
}
void heapify(int a[],int i,int n)//找最大的值，两数换位。有换位时一直遍历到叶子节点
{
	int largest=i;
	int lson=i*2+1;
	int rson=i*2+2;
	if(a[largest]<a[lson]&&lson<n)
	{
		largest=lson;
	}
	if(a[largest]<a[rson]&&rson<n)
	{
		largest=rson;
	}
	if(largest!=i)
	{
		swap(&a[largest],&a[i]);
		heapify(a,largest,n);
	}
}
void heap_sort(int a[],int n)//排序和交换操作
{
	int i;
	for(i=n/2-1;i>=0;i--)//从叶子节点的父节点开始的（即支节点）排序操作。这里i=4时开始构建初始大根堆
	{
		heapify(a,i,n);
	}
	for(i=n-1;i>0;i--)//交换最后一个叶子节点和第一个节点的值，从后面开始向前规律排序
	{
		swap(&a[i],&a[0]);
		heapify(a,0,i);//从头开始往下遍历，维护大根堆性质
	}
}
void print(int a[],int n)//输出
{
	for(int i=0;i<n;i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
}
int main()
{
	int a[10]={2,3,8,1,4,9,10,7,16,14};
	int n=10;
	print(a,n);
	heap_sort(a,n);
	print(a,n);
}

二.解释部分：

关键知识：

递归，交换，排序

小白问：

1.堆排序是在堆里运行的排序吗？

答：不是，堆排序算法的名称来源于它使用了一个数据结构叫做"堆"。但是，这里的"堆"并非指的是计算机内存中的堆（heap），而是一种完全二叉树的一种抽象数据结构。

堆排序算法的实质是通过将待排序的元素构建成一个大根堆（或小根堆），然后反复地将堆顶元素与堆中最后一个元素交换，并调整堆，使得剩余元素仍然满足堆的性质。通过这样的操作，最终可以得到一个有序的序列。

在堆排序过程中，并不直接在内存的堆（heap）上进行排序操作，而是通过对抽象数据结构"堆"的操作来实现排序。堆可以使用数组来表示，通过数组的下标关系来表示节点之间的关系，这样，在堆排序算法中，实际上是对数组元素的位置进行交换和调整，以实现排序的目的。

2.堆排序的优势有什么？

答：堆排序算法具有时间复杂度低、空间复杂度低、稳定性好、适用范围广等优势。在某些场合下，它比其他常见的排序算法更加高效和实用。

复杂度：?

时间复杂度：O(NlogN)

空间复杂度：O(1)

稳定性：相同值的可能不稳定(对于相同的值而言，可能比较后位置不确定)，总体是稳定的（不相等的值时间没有影响）

NO.42

有不完整的内容欢迎评论🌹🌹🌹

<C语言数据结构>?