[数据结构 -- 手撕排序算法第四篇] 堆排序，一篇带你搞懂堆排序

绝地灬酷狼 2023-10-12 11:14 36阅读 0赞

**目录**

1、堆的应用 -- 堆排序

1.1 堆排序的思路分析

2、建堆

2.1 向上调整建堆：O(N\*logN)

2.1.1 向上调整代码

2.1.2 向上调整建堆代码

2.2 向下调整建堆：O(N)

2.2.1 向下调整代码

2.2.2 向下调整建堆代码

3、堆排序实现代码

4、堆排序测试

--------------------

## 1、堆的应用 -- 堆排序 ##

**堆是一个完全二叉树，完全二叉树用数组存储数据最优。**

> 堆排序即利用堆的思想来进行排序，总共分为两个步骤：  
> **1、建堆**
> 
> 升序：建大堆
> 
> 降序：建小堆
> 
> **2、利用堆删除的思想来进行排序**
> 
> 建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

### 1.1 堆排序的思路分析 ###

**我们本篇文章使用小堆进行讲解，小堆排序是降序。**

**对堆还不是很了解的同学可以浅看一下堆的那篇文章：**[戳这里即可跳转][Link 1]

1、我们先对数组里的元素进行向下调整建成小堆；

2、小堆的堆顶元素肯定是数组中最小的，因此我们将堆顶元素（数组首元素）与数组尾元素交换，将数组尾元素不在看作是数组中的元素（size--），再从堆顶开始向下调整重新构建小堆，不断重复就可以实现降序排序（升序只要将小堆改为大堆就可以实现）。

## 2、建堆 ##

**我们建堆可以使用向上调整建堆，也可以使用向下调整建堆，我们该如何选择呢？**

**那肯定是谁的时间复杂度小我就选谁，那接下来我们分析一下两种建堆的时间复杂度：**

### 2.1 向上调整建堆：O(N\*logN) ###

#### 2.1.1 向上调整代码 ####

void AdjustUp(HPDataType* a, int child)
    {
    	int parent = (child - 1) / 2;
    	while (child > 0)
    	{
    		if (a[child] < a[parent])//这里控制大小堆
    		{
    			Swap(&a[child], &a[parent]);
    
    			child = parent;
    			parent = (child - 1) / 2;
    		}
    		else
    		{
    			break;
    		}
    	}
    }

#### 2.1.2 向上调整建堆代码 ####

//建堆 -- 向上调整，时间复杂度：O(N*log(N))
    for (int i = 0; i < size; i++)
    {
    	AdjustUp(a, i);
    }

**我们画图来分析一下向上调整建堆时间复杂度：**

![7300e53a55eb400794ee3b8076dd7240.png][]

**堆是一个完全二叉树，满二叉树也是完全二叉树，因此我们以满二叉树为例推出向上调整建堆的时间复杂度为O(N\*logN)。**

### 2.2 向下调整建堆：O(N) ###

#### 2.2.1 向下调整代码 ####

void AdjustDown(HPDataType* a, int size, int parent)
    {
    	int child = parent * 2 + 1;
    	while (child < size)//当child大于了数组大小就跳出循环
    	{
    		//找出左右孩子中小/大的那个（假设法）
    		if (child + 1 < size && a[child + 1] < a[child])
    		{
    			child++;
    		}
    
    		if (a[child] < a[parent])
    		{
    			Swap(&a[parent], &a[child]);
    
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		else
    		{
    			break;
    		}
    	}
    }

#### 2.2.2 向下调整建堆代码 ####

for (int i = (size - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, size, i);
    }

**我们画图来分析一下向下调整建堆时间复杂度：**

![41983d2505c1340f7963a747d018af3d.png][]

**向下调整建堆时间复杂度：O(N)。**

**如此分析下来我们就可以知道，向下调正建堆才是最优选择。**

## 3、堆排序实现代码 ##

//堆排序时间复杂度O(N + N*logN)
    void HeapSort(int* a, int size)
    {
    	//升序 -- 建大堆
    	//降序 -- 建小堆
    
    	//建堆 -- 向上调整，时间复杂度：O(N*log(N))
    	//for (int i = 0; i < size; i++)
    	//{
    	//	AdjustUp(a, i);
    	//}
    
    	//建堆 -- 向下调整，时间复杂度：O(N)
    	//倒着调整
    	//叶子节点不需要处理
    	//倒数第一个非叶子节点：最后一个节点的父亲开始调整
    	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
    	{
    		AdjustDown(a, size, i);
    	}
    
    	//O(N*log(N))
    	int end = size - 1;
    	while (end)
    	{
    		//1.先交换
    		Swap(&a[0], &a[end]);
    		//2.再调整，选出当前大小的数组中最小数
    		AdjustDown(a, end, 0);
    
    		end--;
    	}
    }

## 4、堆排序测试 ##

**我们建的是小堆，因此最终排的是降序。**

![6c86046f81c045201c2b2031ace61e65.png][]

![7c3e7bac40d5370d3ff4ff7da20481da.png][]

\*\*\* 本篇结束 \*\*\*

[Link 1]: https://blog.csdn.net/Ljy_cx_21_4_3/article/details/130903751
[7300e53a55eb400794ee3b8076dd7240.png]: https://img-blog.csdnimg.cn/img_convert/7300e53a55eb400794ee3b8076dd7240.png
[41983d2505c1340f7963a747d018af3d.png]: https://img-blog.csdnimg.cn/img_convert/41983d2505c1340f7963a747d018af3d.png
[6c86046f81c045201c2b2031ace61e65.png]: https://img-blog.csdnimg.cn/img_convert/6c86046f81c045201c2b2031ace61e65.png
[7c3e7bac40d5370d3ff4ff7da20481da.png]: https://img-blog.csdnimg.cn/img_convert/7c3e7bac40d5370d3ff4ff7da20481da.png