【排序】5.堆排序(详细图解)

文章目录

前言
1.建堆方法的选择
2.优先使用向下调整的原因
3.堆排序图解（大堆-升序为例子）
- 3.1 向下调整法-建大堆
- 3.2 进行堆排序
4.堆排序代码
- 4.1 向下调整法
- 4.1. 1 小堆
- 4.1. 2 大堆
- 4.2 堆排序
5. 关于小堆——降序
6.性能分析

前言

🐱个人主页：代码探秘者
🐭C语言专栏：C语言
🐰C++专栏： C++ / STL使用以及模拟实现/C++11新特性
🐹数据结构专栏：数据结构 / 十大排序算法
🐶 Linux专栏： Linux系统编程 / Linux网络编程（准备更新）
🌈喜欢的诗句:天行健,君子以自强不息.

在这里插入图片描述

1.建堆方法的选择

(1). 建堆
升序：建大堆
降序：建小堆

(2). 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

2.优先使用向下调整的原因

对于最大堆，理论上可以采用向上调整的方法来构建，但实际上并不常用。

这是因为向上调整的方法在构建最大堆时效率较低，时间复杂度为O(nlogn)，与直接插入法相同，而向下调整（堆化）的方法时间复杂度为O(n)，更为高效。

为什么向上调整不常用：

效率问题：如前所述，向上调整建堆的时间复杂度为O(nlogn)，而向下调整建堆的时间复杂度为O(n)。在构建堆时，我们通常希望尽可能高效，因此更倾向于使用向下调整的方法。

操作复杂性：向上调整需要在每次插入新元素后，将新元素与其父节点比较并可能进行交换，直到它找到合适的位置。这个过程涉及到多次的比较和交换，操作相对复杂。

堆的性质：在最大堆中，我们希望较大的值靠近根节点，而较小的值靠近叶子节点。向下调整的方法更自然地符合这一性质，因为它从最后一个非叶子节点开始，逐个向下调整，直到根节点。

3.堆排序图解（大堆-升序为例子）

3.1 向下调整法-建大堆

原始数据为a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}，采用顺序存储方式，对应的完全二叉树如下图所示：
在这里插入图片描述

(1) 选最后一个非叶子结点

在这里插入图片描述

（2）逐个向下调整，直到根节点

3.2 进行堆排序

建好大堆（用我们刚刚上面的从最后一个非叶子结点，从下往上，一直到根结点，进行向下调整法）
把根节点和最后一个结点交换（这样最大的不就放最后了嘛）

在这里插入图片描述

然后从根节点(堆顶)，又继续向下调整

这样20是最大的，就排好在最后了
之后交换5和17
然后向下调整，这样排好17,交换3和16
交换好，然后向下调整，继续交换5和4，调整后，
交换4和3，然后调整
这样就完成了！

在这里插入图片描述

4.堆排序代码

4.1 向下调整法

4.1. 1 小堆

我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。

选出最小的孩子
最小孩子比父亲小，就交换上来
更新parent和minchild，一直循环到最后

//向下调整:从哪里开始
//删除调用
void AdjustDown(DataType* a, int n, int parent)
{//先找到最小的孩子int minchild = 2 * parent + 1;	//假设左孩子最小while (minchild < n){//右孩子存在，而且小于左孩子if (minchild + 1 < n && a[minchild + 1] < a[minchild]){minchild++;		//更新最小为右孩子}//开始向下调整//小堆为例)if (a[minchild] < a[parent]){Swap(&a[minchild], &a[parent]);	//交换//更新parent和minchildparent = minchild;minchild = 2 * parent + 1;}else{break;}}
}

4.1. 2 大堆

选出最大的孩子
最大孩子比父亲大，就交换上来
更新parent和minchild，一直循环到最后

//向下调整:							从哪里开始
//删除调用
void AdjustDown(DataType* a, int n, int parent)
{//先找到最大的孩子int maxchild = 2 * parent + 1;	//假设左孩子最小while (maxchild < n){//右孩子存在，而且大于左孩子if (maxchild + 1 < n && a[maxchild+ 1] > a[maxchild]){maxchild++;		//更新最大为右孩子}//开始向下调整//大堆为例if (a[maxchild] > a[parent]){Swap(&a[maxchild], &a[parent]);	//交换//更新parent和minchildparent = maxchild;maxchild = 2 * parent + 1;}else{break;}}
}

4.2 堆排序

//交换
void Swap(DataType* px, DataType* py)
{DataType tmp = *px;*px =*py;*py = tmp;
}void HeapSort(int* a, int n)
{//向上调整建堆 不推荐nlogn// 	for (int i = 1; i < n; i++)//{//	AdjustUp(a, i);//}//向下调整建堆 O(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;		//排好一个}
}
void HeapSortTest()
{int a[] = { 50,100,70,65,60,32 };int n = sizeof(a) / sizeof(a[0]);HeapSort(a, n);for (int i = 0; i < n; i++){printf("%d ", a[i]);}
}