【C语言】五分钟快速了解堆排序！_堆排序c语言

堆排序

一.前言

二.堆的建立

1.数组中父节点与子节点的关系

2.向下调整建堆法

①条件

②建堆思路

③实现代码

④建堆效果

三.堆的排序

①排序思路

②实现代码

③排序效果

四.时间复杂度

五.源码分享

---

一.前言

堆排序，顾名思义，对堆进行排序，那么问题来了，没有堆怎么排序呢？那就建堆好啦！所以，堆排序首先就得对排序目标建堆，然后再对建好的堆进行排序。本文将演示对数组的升序堆排序！

堆排序中升序要用到大堆根；而降序则要用到小堆根。

二.堆的建立

1.数组中父节点与子节点的关系

如果父节点的下标为n，那么子节点的下标就为2n+1、2n+2；

如果子节点（不论左孩子右孩子）的下标为n，那么父节点的下标就为（n-1）/2。

具体推导过程可以自己试着求一下哦~

2.向下调整建堆法

①条件

除调整数字外，该数字的所有子节点都为堆。

②建堆思路

在调整每个父节点之前，把子节点都建好堆。也就是从最后一个父节点开始，往前走一个一个地建堆。

③实现代码

//两数交换
void Swap(int* a, int* b)
{
	int s = *a;
	*a = *b;
	*b = s;
}
 
//向下调整堆
void AdjustDown(int* a, int size, int i)
{
	int parent = i;
	int child = parent * 2 + 1;
	while (child < size)
	{
		// 升序，取两孩子中大的那个与父节点比较
		if (child + 1 < size && a[child + 1] > a[child])
			child++;
		// 升序，如果子节点比父节点大，则交换
		if (a[child] > a[parent])
			Swap(&a[child], &a[parent]);
		else
			break;
 
		// 子节点变为父节点，进行下一轮比较
		parent = child;
		child = parent * 2 + 1;
	}
}
 
//堆的创建
void HeapCreate(int* a, int n)
{
	assert(a);
	int child = n - 1;					// 找到最后一个子节点
	int parent = (child - 1) / 2;		// 找到最后一个父节点
	for (int i = parent; i >= 0; i--)	// 从最后一个父节点开始到第一个父节点结束建堆
	{
		AdjustDown(a, n, i);			// 向下调整堆
	}
}

除了向下调整建堆法，还有一个向上调整的，不过其时间复杂度跟冒泡有一比，那就不多赘述啦！

④建堆效果

对调整后的数组画图检测一下：

三.堆的排序

①排序思路

已经知道最大数在堆首啦，而刚好要升序，那么，把堆首和堆尾交换一下不就好了嘛。

交换以后，将除最后一个元素的数组都视为堆，再对整个堆向下调整，便又获得一个新的大堆啦！

然后不断循环循环，每次堆首的最大值都往后放，直到遇到堆首便排序完毕了。

②实现代码

//堆排序
void HeapSort(int* a, int n)
{
	//建堆
	HeapCreate(a, n);
	//排序堆
	for (int i = n; i > 0; i--)
	{
		Swap(&a[0], &a[i - 1]);
		AdjustDown(a, i - 1, 0);
	}
}

③排序效果

 到这里堆排序便圆满结束啦！

四.时间复杂度

堆排序的时间复杂度为O(NlogN)：

向下调整建堆的时间复杂度为O(N)；

调整最大数并调整堆的时间复杂度为O(N^2)。

五.源码分享

//两数交换
void Swap(int* a, int* b)
{
	int s = *a;
	*a = *b;
	*b = s;
}
 
//向下调整堆
void AdjustDown(int* a, int size, int i)
{
	int parent = i;
	int child = parent * 2 + 1;
	while (child < size)
	{
		// 升序，取两孩子中大的那个与父节点比较
		if (child + 1 < size && a[child + 1] > a[child])
			child++;
		// 升序，如果子节点比父节点大，则交换
		if (a[child] > a[parent])
			Swap(&a[child], &a[parent]);
		else
			break;
 
		// 子节点变为父节点，进行下一轮比较
		parent = child;
		child = parent * 2 + 1;
	}
}
 
//堆的创建
void HeapCreate(int* a, int n)
{
	assert(a);
	int child = n - 1;					// 找到最后一个子节点
	int parent = (child - 1) / 2;		// 找到最后一个父节点
	for (int i = parent; i >= 0; i--)	// 从最后一个父节点开始到第一个父节点结束建堆
	{
		AdjustDown(a, n, i);			// 向下调整堆
	}
}
 
//堆排序
void HeapSort(int* a, int n)
{
	//建堆
	HeapCreate(a, n);
	//排序堆
	for (int i = n; i > 0; i--)
	{
		Swap(&a[0], &a[i - 1]);
		AdjustDown(a, i - 1, 0);
	}
}
 
int main()
{
	int a[] = { 10,8,9,3,5,4,6,2,1,7 };
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
 
	HeapSort(a, sizeof(a) / sizeof(a[0]));
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		printf("%d ", a[i]);
	}
 
	return 0;
}