堆排序

首先堆排有几个关键的步骤
①创建堆 ②调整堆

创建堆

创建堆的方式有两种①向上调整建堆 ②向下调整建堆

①首先我们来看第一种:向上调整建堆

这种方式的原理就是看作最开始堆中只有一个元素,从第一个元素开始就已经在向上调整,然后逐渐像堆中加入元素,随着一个一个元素的加入,也就形成了堆
图解如下:

而代码就是通过AdjustUp函数和一个for循环就可以完成上面步骤

//以前n个数建小堆
for (int i = 0; i < n; ++i)
{
	AdjustUp(a, i);  //a为数组的指针
}

时间复杂度: O(n*logn)

分析:首先我们上面详细分析了AdjustUp()的时间复杂度为O(logn),然后循环了n此每次建堆,所以两者相乘,时间复杂度也就是 n*logn 了

---

②我们来看第一种:向下调整建堆 -----堆排序中最主要用到的方法

这种建堆的关键就是从倒数第一个非叶子节点开始调(也就是树中最后一个父节点),然后逐渐+1,就可以调整从最后一个父节点开始的每一棵树.
不难发现这样也符合向下调整的前提,即左右子树都是堆
那么我们如何找到最后一个节点的父亲?
就需要用到公式:Parent = (Child - 1) / 2;
图解如下

而代码就是通过AdjustDown函数和一个for循环就可以完成上面步骤

for (int i = ((n-1)-1)/2; i >= 0; --i) 
//(n-1)是拿到树最后一个节点,然后再根据公式Parent = (Child - 1) / 2;
{
	AdjustDown(a, size, i);
}

时间复杂度:O(n)
根据下面的思路

因此建堆的时间复杂度为O(n)

总结????:其实两种方式建堆之所以时间复杂度有差距,就是因为向下调整建堆可以看作忽略了最后一排的节点,直接从倒数第二排节点开始调整的,而在一棵满二叉树中最后一排的节点其实就占据了整棵树的二分之一,所以相当于向下调整比向上调整少经历了很多的节点
所以实际堆排序中我们更多的使用的是向下调整建堆,因此时间复杂度为O(n)

还有一点需要注意的是:如果你想要升序,即从小打大,需要建大堆.
建了大堆之后,再交换首元素(最大的)和末尾元素,然后把最大的元素不算入堆中的元素,
再进行向下调整
如果你建小堆,当你拿到首元素(最小的元素之后),需要将数组依次前移然后重新建堆,每次都前移然后每次都建堆,时间复杂度直接拉满!!!
同理 如果你想要降序,即从大打小,需要建小堆.

---

调整堆

在堆建好之后,就可以开始调整堆了,比如你是升序,即从小打大,需要建大堆.
建了大堆之后,循环N次 ，进行N次调整堆操作，每一次调整 堆得到的最大值，将此值和数组的最后一个元素进行交换，交换减小数组的长度（最后被减小的那几个值不参与堆的调整），直到最后一个元素，就完成了堆的排序.

如下图,降序—小堆, 展示了其中一个调整过程

整合步骤

综合建堆和调整,完整的堆排序代码就出来了

void HeapSort(int* a, int n)
{
	// 建堆 （大堆）or  （小堆）
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}
int end = n - 1;
while (end > 0)
{
	Swap(&a[0], &a[end]);  //交换
	AdjustDown(a, end, 0); //向下调整
	--end;   //换下来的最后一个数不计入堆中
}

升序建大堆,降序建小堆很重要!