【排序】堆排序（C语言实现）

---

?
?
?

前言

---

本章主要会讲堆排序的实现过程以及向上调整和向下调整的时间复杂度，在学习本章前，需要对堆、以及向上调整和向下调整有一个了解，如果不了解的话可以先看看这篇文章：《堆的实现及TOP-K问题》

?
?

1. 堆排序

---

1.1 堆排序的思想

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

这里以升序为例：我们通过一个向下调整的算法建一个大堆，然后将第一个数据和最后一个数据交换一下，以此类推，把大的数往后面放。

?

1.2 堆排序的实现

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

我们用代码来实现一下它的逻辑：

// 向下调整
void AdjustDown(int* a, int size, int parent) // 建大堆
{
	int child = parent * 2 + 1; // 左孩子

	while (child < size)
	{
		// 判断左孩子和右孩子哪个大,就令child等于哪个孩子
		if (child + 1 < size && a[child] < a[child + 1]) 
		{
			++child;
		}
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break; // 如果父亲和孩子不用交换,就代表已经排好了,不需要再往后比较
	}
}

void HeapSort(int* a, int n)
{
	// 建一个大堆
	for (int i = (n - 1 - 1) / 2;i >= 0;i--)
	{
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end >= 0)
	{
		Swap(&a[0], &a[end]); // 将堆顶元素换到最后一个位置
		AdjustDown(a, end, 0); // 左闭右开区间
		--end; // 调整end的位置
	}
}

?
?

2. 为什么向下调整而不是向上调整

---

上面堆排序的时候，不论是建堆还是排序的时候使用的是向下调整的算法，那么为什么不用向上调整的算法呢？

在这里我们先来看一下向下调整算法：

再来看看向上调整算法：

很明显，我们可以看出向下调整的时间复杂度是要比向上调整算法的时间复杂度低的，所以我们只要掌握住向下调整算法就可以了，向上调整算法就当做个了解。