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

发布时间:2024年01月03日

?一.代码部分:

//堆排序
#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语言数据结构>?

文章来源:https://blog.csdn.net/m0_74000825/article/details/135352886
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。