【数据结构】八大排序之堆排序算法

🦄个人主页:修修修也

🎏所属专栏:数据结构

??操作环境:Visual Studio 2022

---

目录

一.堆排序简介及思路

二.堆排序的代码实现

三.堆排序的时间复杂度分析

结语

---

一.堆排序简介及思路

堆排序(Heap Sort)是一种效率较高的选择排序算法.

它是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它通过堆来进行选择数据.

有关堆还不了解的朋友可以先移步这篇文章:【数据结构】什么是堆?

它的基本思想是:

1. 将待排序的序列构造成一个大堆.(如果是降序则建小堆)
2. 此时,整个序列的最大值就是堆顶的根结点.将它移走(其实就是我们前面堆实现中的出堆顶操作).
3. 然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素中的次小值(即堆顶).
4. 如此反复执行,就可以得到一个有序的序列了.

算法动图演示:

1.向下调整建堆

逻辑结构:

物理结构:

2.堆排序(升序)

逻辑结构:

物理结构:

---

二.堆排序的代码实现

算法实现步骤:(以升序为例)

1. 从最后一个叶子结点的双亲节点开始向前遍历并向下调整建堆.
2. 建堆完成后,将堆顶元素与待排序列的最后一个元素做交换.
3. 交换后缩小待排序列范围,使刚刚交换到最后的堆顶元素不再参与后续的堆排序.
4. 重新将新堆顶元素向下调整,使堆恢复为大堆.
5. 重复2-4步骤,直到数组完全有序.

搞清实现步骤后,代码的实现就比较简单了,堆排序代码如下:

//交换函数
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

//向下调整建堆
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;//默认是左孩子
	while (child < n)//孩子走到叶子就可以停止了
	{
		//选出左右孩子中大的那个
		if (child + 1 < n && a[child + 1] > a[child])//如果右孩子存在且大于左孩子
		{
			child++;
		}
		//向下调整重新使堆有序
		if (a[child] > a[parent])//建大堆
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


//堆排序(升序
void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)//先向下调整建堆
	{
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[end], &a[0]);//将堆顶元素和待排区间的最后一个元素交换

		AdjustDown(a, end, 0);

		end--;
	}
}

---

三.堆排序的时间复杂度分析

堆排序方法对数据数较少的序列排序的效果并不很好,但对n较大的序列还是很有效的.

因为它的运行时间主要耗费在建初始堆和调整建堆时进行的反复"筛选"上.

???????? 对深度为k的堆,筛选算法中进行的关键字比较次数至多为2(k-1)次,则在建含n个元素,深度为h的堆时,总共进行的关键字比较次数不超过4n.又因为n个结点的完全二叉树的深度为,则调整建新堆时调用向下建堆函数过程n-1次,总共进行的比较次数不超过下式:

因此,堆排序在最坏的情况下,其时间复杂度也为O(nlogn),这是相对快排,堆排的最大优点.

---

结语

希望这篇堆排序算法详解能对大家有所帮助,欢迎大佬们留言或私信与我交流.

有关更多排序相关知识可以移步:

【数据结构】八大排序算法??https://blog.csdn.net/weixin_72357342/article/details/135038495?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22135038495%22%2C%22source%22%3A%22weixin_72357342%22%7D&fromshare=blogdetail

学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!

相关文章推荐

【数据结构】八大排序之冒泡排序算法

【数据结构】八大排序之希尔排序算法

【数据结构】八大排序之直接插入排序算法

【数据结构】八大排序之简单选择排序算法

---

数据结构排序算法篇思维导图:

---