C语言版堆排序代码讲解（超级详细）-创新互联

先说什么是堆呢，堆是一种完全二叉树，它分为大堆和小堆，堆的表示最好用数组表示，因为它是完全二叉树，不存在分支为空

做堆之前，要熟练掌握两个公式  parent=（child-1）/2；

child=parent*2+1;

这里我们拿升序的代码举例，记住，升序就要大堆，降序就要小堆，具体为何看代码注释

这里建议先看代码，代码看不懂再看图解

AdjustUp的图解---这个图解的过程得配合HeapPush这个函数看，插入一个，就调整一次，这里的child永远是数组最后一个元素

以此类推，只要记住child永远是数组最后一个，然后插入一次调整一次就行了

AdjustDown图解--建议这个函数的图解配合Heapsort函数的第一个循环看更好，我写的可能跟那个函数的意思不一样，不过都大同小异，理解了我的图解，再想一下就好了

以此类推

Heapsort图解

​
#include#include#include
typedef int HPDataType;
//先创建一个堆的结构体
typedef struct Heap
{
	HPDataType* a;
	int size;//元素的个数
	int capacity;//这块空间的大承受元素的限度，说到这里有的小伙伴可能还是不懂，那么我就来举个例子吧
	//比如你创建了一块空间，可以容下10个元素，这时候有一个数组里面有5个元素，那么相对于这个结构体来说，size就是5，capacity就是10
}HP;
//对堆进行初始化，这个大家应该都能理解，我也不解释了
void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}
//交换函数，下面会用到多次交换，所以我就写了一个交换函数，交换函数大家应该都能理解，我也不多解释了
void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}
//这个函数是向上调整
void AdjustUp(int* a, int child)
{
	//child就是最后一个元素的下标，然后用公式把他的parent求出来
	int parent = (child - 1) / 2;
	while (child >0)
	//这里有人会问了，为什么不能是parent>=0,而是child>0呢
	//你想，由大括号里面的这两个公式
	// child = parent;
	//parent = (child - 1) / 2;
	//到最后，parent=0的时候，把parent赋值给child，然后这时候child就是0了
	//然后parent = (child - 1) / 2的时候，child是0，（0-1）/2还是0；
	//所以只要控制child>0就好了
	{
		if (a[child] >a[parent])//记住，大堆这里就改成>，小堆就是<，a[child]和a[parent]的顺序最好不要变（可以变），容易给自己搞懵！！
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//这个函数是往数组堆的结构体里面的那个HPDataType* a里面一个一个放进去main()函数里的数组arr中的元素
void HeapPush(HP* hp, int x)
{
	if (hp->size == hp->capacity)//如果这个时候size跟capacity（这块空间的元素的个数跟这块空间所能承受的元素的大限度相等了）
	{
		//就需要扩容了，如果空间所能承受的元素的大限度是0，那么就扩容四个空间
		//如果空间所能承受的元素的大限度不是0，那么就在原来空间所能承受大限度的基础上再扩容一倍
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		 //下面这个语句的意思就是增容
		//为什么tmp的类型是 HPDataType*呢？？我们接着往下看，realloc的意思就是把一个空间，在它原有的基础上
		//增容到realloc的括号里面的逗号后面那个对象的大小，这里也就是sizeof(HPDataType) * newcapacity
		//增容到sizeof(HPDataType) * newcapacity这么大
		//回到刚才那个问题，这里结构体的int* a你可以认为是一个数组
		//[(HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity)]的意思要把数组里面的元素增容到这么大，然后将这个赋值给tmp,
		// 这时候tmp就可以认为成一个数组了，这个数组里面的元素的大容量比a数组里面的大
		//并且tmp在下一步要赋值给a
		


		//有的人想问了，为什么不直接写(hp->a,newcapacity)呢，我自己的理解是，我们创建的堆的结构体里面
		//a数组里面的数据类型都是HPDataType，这里我把int给typedef成HPDataType，也就是说HPDataType也占四个字节
		//你的一个数组里面就算是有int类型的元素，但是他们每个元素都是4个字节，比如你有一个10个元素的数组，它里面是40个字节，同样
		//你增容后的数组也要按照字节来算，计算机里面是按照字节的，不是按照元素个数的
		HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)//判断一下tmp是否增容成功了
		{
			printf("realloc failed\n");
			exit (-1);
		}
		hp->a = tmp;//相当于把tmp数组的容量大小赋值给a数组了
		hp->capacity = newcapacity;//然后把newcapacity的值赋给capacity
	}
	hp->a[hp->size] = x;//hp->size就是数组最后一个元素的后面紧挨着的那个空间
	hp->size++;//插入了之后，元素的个数+1

	//下面这个向上调整可以加上可以不加上
	// hp->a就是把a这个数组传过去，hp->size-1就是最后一个元素的下标
	//AdjustUp(hp->a,hp->size-1);
}
//打印函数，把元素一个个打印出来，验证你的代码是否正确
void Print(HP* hp, int sz)
{
	for (int i = 0; i< sz; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}//这个是向下调整
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	//这里child没分左右孩子，默认为左孩子
	while (child< n)
	{
		//child+1肯定是右孩子
		if (child + 1< n && a[child + 1] >a[child])//还是一样，大堆就是a[child + 1] >a[child]，小堆就是<，顺序最好别变，否则易懵
		{
			child++;
		}
		if (a[child] >a[parent])//大堆就是a[child] >a[parent]，小堆就是<
		{
			Swap(&a[child], &a[parent]);
			parent = child;//相应的顺序大家看AdjustUp,思想都差不多
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void Heapsort(HP* hp, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
		//(n - 1 - 1)的意思就是，最后一个孩子的父亲，n-1是最后一个孩子，把它看成N
		//然后（N）-1/2不就是我说的公式嘛
		//这个时候arr数组中的元素都已经相应的插入到a里面去了，但是还是乱序，不知道它是大堆还是小堆，这里我们要把它调成大堆，因为是升序
		//i= (n - 1 - 1) / 2意味着我们只需要从倒数第一个非叶子结点调整，如果我们从叶子结点调整的话，叶子结点也没有孩子呀，码农们想一下
		//这时候i--的意思就是调整完倒数第一个非叶子结点之后，就开始调整倒数第二个非叶子结点
	{
		//hp->a表示传数组，n表示传元素的个数，i表示开始调整大堆的位置
		AdjustDown(hp->a, n, i);
	}
	//上一行代码---也就是}这个大括号的右半部分结束之后，我们的大堆就调好了
	//下一行代码就是要开始排序了
	for (int end = n - 1; end >0; end--)
	{
		//你想，hp->a[0]肯定是这个堆里面的大的一个，然后把这个大的一个跟堆里面最后一个进行交换
		Swap(&hp->a[0], &hp->a[end]);
		//换完了之后，最后一个换到了第一个，这个时候乱序了，肯定不是大堆了，这个时候就开始把第一个向下调整
		//hp->a表示传数组，end表示传元素的个数，0表示开始调整大堆的位置
		AdjustDown(hp->a, end, 0);
		//调整完了之后又是一个大堆了，这个时候数组最后一个元素大，所以end--，这个时候相当于不要数组最后一个元素了，大的已经找到了
		//然后，这个不要最后一个元素之后，第一个元素就是大的了，然后再进行循环
		
		
		//为什么end不是>=0呢，你想，假如有5个数字，大的4个数字都找出来了，最后一个肯定是最小的呀
	}
}
int main()
{
	HP hp;
	HeapInit(&hp);
	int arr[] = { 50,20,90,100,1,65,88 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i< sz; i++)//把这个数组里面的元素一个个插入到HPDataType* a里面去
	{
		HeapPush(&hp,arr[i]);
	}
	Print(&hp, sz);
	Heapsort(&hp, sz);
	Print(&hp, sz);
	return 0;
}

​

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧