堆排序详解（C语言）

文章目录

• 对数组建堆的两种算法
• • 向上建堆
  • 向下建堆
• 两种建堆算法的时间复杂度
• • 用向上调整算法建堆时间复杂度
  • 用向下调整算法建堆时间复杂度
• 堆排序
• • 升序排序
  • 降序排序

在 堆的实现这篇文章的最后，讲解了堆排序的一种实现。实现算法的时间复杂度为O(N * logN)，空间复杂度为O(N)，总的来说该算法不是特别优秀，还需要优化到空间复杂度为O(1)。

在优化前需要知道空间复杂度为O(1)的两种对数组建堆的算法。

对数组建堆的两种算法 向上建堆

从数组的第二个元素开始，向上建堆。之前实现堆时写过一个向上调整的接口，AdjustUp(HDataType* data, size_t child)，该接口将data数组中以child为下标的元素向上调整，调整后的数组从0到child下标之间的数在逻辑上可以看作一个堆。假设我们要建立的堆是小堆，该接口会比较子节点与父节点的大小，子节点小于父节点，交换两节点。

如下图的数组

第二个节点向上调整后

第三个节点大于其父节点，不交换；第四个节点为4，其父节点9，子节点小于父节点，交换。
最后被换到根的位置…循环下去直到遍历所有的数，这样对数组的建堆并且其空间复杂度为O(1)的算法就完成了。

验证堆是否正确

向下建堆

利用之前写的AdjustDown接口，AdjustDown(HDataType* data, size_t size,size_t root)，该接口将root向下调整，使得数组从以root为下标的元素到最后一个元素构成一个堆。由于叶节点没有子节点，无法向下调整，所以只需要从数组中第一个叶子节点的前一个节点开始，调用AdjustDown接口，往回遍历数组，这样空间复杂度为O(1)的建堆算法就完成了。

第一个叶子节点的前一个节点，也就是最后一个节点的父节点。size是数组的大小，size-1是最后一个节点的下标，根据之前的知识，((size - 1) - 1 )/ 2得到最后一个节点的父节点。

循环进行五次，从2开始，到9结束。

验证结果是否为小堆

两种建堆算法的时间复杂度 用向上调整算法建堆时间复杂度

假设一个堆有h层，每一层的节点数都是有规律的。在向上调整建堆的算法中，数组中的每一个节点都要与其父节点进行比较，从最坏的情况考虑，节点会一直比较到根节点。

则向上调整的累计次数：T(n) = 2^1 * 1 + 2^2 * 2 + 2^3 * 3 + … + 2^ (h - 1) * (h - 1)，可以理解成每层的节点个数乘以要比较的次数

利用错位相减法，将T(n) * 2 - T(n)得到2^h * (h - 2) + 2，h是堆的层数，2^h - 1 = n，所以h = log(n + 1)。带入结果，（n + 1) * (log(n + 1) - 2) + 2。用渐近表示法，得到向上调整算法的时间复杂度为O(n * logn)。

用向下调整算法建堆时间复杂度

由于叶节点不用调整，所以要调整的节点范围在倒数第二层往上到根节点。第一层节点要调整的次数：2^0 * (h - 1)，第二层：2^1 *(h - 2)…到第h - 1层：2^(h - 2) *1。

T(n) = 2^0 * (h - 1) + 2^1 *(h - 2) + 2^(h - 2) *1

用错位相减法得到T(n) = 2^h - h - 3。将h化为n得到：n - log(n + 1) + 2。所以向下调整算法的时间复杂度为O(n)。

堆排序 升序排序

首先排序的前提是：不开辟额外的空间，在原数组中排序。

一个数组要以升序的方式排序，是建立大堆还是小堆？如果建立小堆，堆顶（也就是数组的首元素）是最小的数，要保证第二个元素是最小的，只能将除了第一个元素之外的数再建成一个小堆，若用向下调整算法（时间复杂度为O(n)，对一个有n个元素的数组以建立小堆的方式排序，每次取堆顶的数，将其他数再建立成一个小堆，再取堆顶的数，这样循环，时间复杂度为O(n^2)，一个算法的时间复杂度是指数次，那这个算法就是垃圾。还比如遍历数组找最小，将最小的数放到数组的前面。所以建立小堆来升序排序是想不通的。

升序排序建立大堆，大堆的根为数组中最大的数，将其与数组最后一个数交换，此时的堆顶是交换后的数，需要再次调整，保证除了最后的数，剩下的数是一个大堆。这样重复下去，这种算法的好处就是没有改变其他数之间的父子关系，而重新建立小堆是改变了所以数之间的父子关系，时间开销大。

如图是一个大堆，在升序排序前将数组建立成一个大堆。将第一个数9，与最后一个数3交换，数组的长度要减1，此时9不再是堆中的一员

红线部分是要建立的大堆，此时除了堆顶3，3的左子树与右子树仍然是一个大堆

蓝色部分依旧满足大堆的性质。所以对堆顶的3进行向下调整后，除了9之后的数又组成了一个大堆，再把堆顶的数与最后一个数交换，再调整堆顶…这样循环下去直到数组的长度为1，此时剩下一个数也没节点和他交换，所以循环结束。

代码实现

void Swap(HDataType* num1, HDataType* num2)
{
	HDataType tmp = *num1;
	*num1 = *num2;
	*num2 = tmp;
}

//建大堆的向下调整
void AdjustDown(HDataType* data, size_t size, size_t pos)//pos是要进行向下调整的数的下标
{
	assert(data);
	
	size_t parent = pos;
	size_t child = parent * 2 + 1;
	while (child < size)//若孩子节点的下标小于数组长度，则循环继续
	{
		if (child + 1 < size && data[child + 1] > data[child])//若右孩子	存在并且右孩子大于左孩子，则修改child，将child指向右孩子
		{
			child++;
		}
		if (data[parent] < data[child])//若父节点小于子节点，交换两节点
		{
			Swap(&data[parent], &data[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;//若父节点大于子节点，满足堆的性质，不用调整
		}
	}
}

void HeapSort(HDataType* data, size_t size)
{
	assert(data);
	for (int i = (size - 2) / 2; i >= 0; i--)
	{
		AdjustDown(data, size, i);
	}
	while (size > 0)
	{
		Swap(&data[0], &data[size - 1]);
		size--;
		AdjustDown(data, size, 0);
	}
}

降序排序

排升序用大堆，降序的话则是用小堆。先用数组的数建立一个小堆，将堆顶与数组的最后一个数交换，交换后将除了最后一个数之外的其他数看成一个小堆，当然此时的堆顶不满足小堆的性质，所以需要对堆顶进行向下调整。过程与升序排序类似。

代码实现

void Swap(HDataType* num1, HDataType* num2)// 交换两数的接口
{
	HDataType tmp = *num1;
	*num1 = *num2;
	*num2 = tmp;
}

// 将长度为size的数组中下标为pos的数向下调整
void AdjustDown(HDataType* data, size_t size, size_t pos)
{
	assert(data);

	size_t parent = pos;
	size_t child = parent * 2 + 1;// 假设左孩子是两节点中较小的
	while (child < size)
	{
		// 若右孩子存在并且右孩子小于左孩子，将child指向右孩子
		if (child + 1 < size && data[child + 1] < data[child])
		{
			child++;
		}
		// 若父节点大于子节点，交换两数
		if (data[parent] > data[child])
		{
			Swap(&data[parent], &data[child]);
			parent= child;
			child = parent * 2 + 1;
		}
		else// 父节点小于子节点，满足小堆性质，不交换
		{
			break;
		}
	}
}

void HeapSort(HDataType* data, size_t size)
{
	assert(data);
	
	for (int i = (size - 2) / 2; i >= 0; i--)// 将数组中的数建成一个小堆
	{
		AdjustDown(data, size, i);// 从叶节点的前一个节点开始向下调整
	}

	while (size > 1)	
	{
		Swap(&data[0], &data[size - 1]);
		size--;// 最后一个数不算是堆中的数
		AdjustDown(data, size, 0);// 调整堆顶元素
	}
}
	
```