【C语言数据结构】堆排序详解（二叉树之堆的排序）_小分堆的排序c语言代码

目录

一、底层逻辑

        升序

        降序

二、实现堆排序

三、时间复杂度

向上调整

向下调整

总结

---

一、底层逻辑

堆排序就是利用堆的思想来进行排序，总共分为两个步骤：

1.建堆

        升序建大堆；

        降序建小堆

2.利用堆删除的思想来进行排序

        利用向下调整操作

为什么？

        根结点最大叫做大堆，根结点最小叫做小堆。升序是要让根结点最小之后依次递增，降序是要让根结点最大之后依次递减。照这么看升序建小堆，降序建大堆才更合理。誒，可不敢想简单了，我们需要从堆的结构入手考虑：

        升序

        上一篇我有写到大堆的实现，其中大堆的删除中用到了向下调整操作，就是把堆顶放到堆尾进行删除，再将堆进行调整使它的堆顶结点最大。向下调整操作在排序这里同样适用：通过交换首尾结点，最大值来到了堆尾，再通过调整将老二放到堆顶，再进行新一轮交换、调整，最后堆顶会变成最小值，依次递增，升序排序就实现了。    

        重复上图中的操作后的堆：

                         

        降序

        同样的，首先交换首尾，最小值来到了堆底 ，然后进行向下调整，将第二小的值放到堆顶，之后重复操作，直到最大值来到堆顶，依次递减，就这样实现了降序。

        重复上图操作之后的堆：

                          

        由此可见，小堆排降序，大堆排升序，充分利用到了堆的性质。清楚了底层逻辑，我们就可以用代码来实现了。

二、实现堆排序

        首先我们定义一个数组，然后需要把它变成一个大堆或者小堆，实现的方法就是向上调整，向上调整的方法在上一篇博客堆的实现的插入数据操作中有详解，跳转链接在这，也可以看图理解

         在建堆完毕之后，我们需要做的就是上述讲到的向下调整方法，需要注意的是，交换首尾结点之后，原尾结点不算作数组当中，即尾结点不看做某一结点的子结点，循环操作直到最小值（或者最大值）来到了首结点，我们就实现了升序（或者降序）。

#include<stdio.h>
 
//结点数据的交换
void Swap(int* A, int* B)
{
	int tmp = *A;
	*A = *B;
	*B = tmp;
}
//堆的向上调整
void AdjustUp(int* php, int child)	
{
	int parent = (child - 1) / 2;
	while (child)
	{
		if (php[parent] < php[child])//大堆用“<”，小堆用“>”
		{
			Swap(&php[parent], &php[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}
 
//升序或降序
void HeapSort(int* a, int x)
{
	//建堆
	for (int i = 0; i < x; i++)
	{
		AdjustUp(a, i);
	}
	//向下调整
	int size = x - 1;
	while (size)
	{
		if(a[0]>a[size])//降序改成<
			Swap(&a[0], &a[size]);
		size--;
		int i = 0;
		while (i * 2 + 2 <= size)
		{
			if (a[i] > a[i * 2 + 1] && a[i] > a[i * 2 + 2])//降序改成两个<
				break;
			if (a[i * 2 + 1] >= a[i * 2 + 2])//降序改成<=
			{
				Swap(&a[i * 2 + 1], &a[i]);
				i = i * 2 + 1;
			}
			else
			{
				Swap(&a[i * 2 + 2], &a[i]);
				i = i * 2 + 2;
			}
		}
	}
	return;
}
 
int  main()
{
	int a[15] = { 5,7,9,8,6,0,3,2,4,1,-1,-2,0,1,15 };
	HeapSort(a, 15);
	return 0;
}

        来看看升序的结果：

         我们把上述代码中注释处的 > 修改成 < 就可以实现降序了：

三、时间复杂度

        说到排序，我们不容忽视的一个事情就是关于它的时间复杂度，排序方法有很多，时间复杂度是我们进行比较选择的一个重要参数，那么堆排序的时间复杂度是多少呢？

先给出答案：O(N)=n*logn

再来谈谈为什么：

来看代码，考虑时间复杂度，我们需要注意的有两处，一处是建堆，一处是向下调整。

        建堆与向下调整操作是并列的，而建堆用的是向上调整操作，所以最终堆排序的时间复杂度就是向上调整操作与向下调整操作的时间复杂度的较大者。

向上调整

        我们假设堆的深度是h，结点个数是n。我们不妨把每一层的结点数都用深度表示出来

h=1         n=2^0

h=2         n=2^1 

h=3         n=2^2

...

h=h         n=2^(h-1)

       

        结点数n和深度h的关系就可以表示了。

        向上调整时间复杂度O(N)就是假设每个结点都需要向上调整到堆顶，全部结点所需要向上调整的次数总和就是O(N)。我们已经知道了每一层的结点数，再把他们向上调整的次数加起来就可以了。第h层需要调整的次数最多，是h-1次，层数越往上，次数依次递减，直到第二层只需要调整1次。总共的调整次数设为T(N):T(N)=2^1*1+2^2*2+……+2^(h-1)*(h-1)。看到这个式子有没有点熟悉感，没错，它是一个等差比数列，我们可以用错位相减的方法来进行化简：

最终的化简结果是：T(N)=2^h*(h-3)+2

        但是这不是我们想要的结果呀，我们想要的应该是用n来表示T(N)，但这里是h，不过我们不是知道了n和h的关系式了吗，替换掉就可以了。

最终得出向上调整时间复杂度：O(N)=n*logn

向下调整

        同样的，将深度h和结点数n的关系表示出来：

        然后假设每一个结点都需要向下调整到堆底，第1层的结点需要调整h-1次，第2层h-2次，……，第h-1层只需要1次。 总调整次数最后可以表示出来:

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

同样是一个等差比数列，用错位相减法进行化简：

 用n来替换h：

 最后得到向下调整的时间复杂度：O(N)=n

总结

        综上所述，堆排序的时间复杂度：O(N)=n*logn