当前位置:   article > 正文

【数据结构】(6.3)堆的应用——堆排序(C语言)

【数据结构】(6.3)堆的应用——堆排序(C语言)

系列文章目录

`


`


前言


1. 堆排序的基础知识

堆排序(Heap Sort)就是对直接选择排序的一种改进。此话怎讲呢?直接选择排序在待排序的n个数中进行n-1次比较选出最大或者最小的,但是在选出最大或者最小的数后,并没有对原来的序列进行改变,这使得下一次选数时还需要对全部数据进行比较,效率大大降低。

堆排序算法Floyd和Williams在1964年共同发明的,同时他们发明了“堆”这种数据结构。

2. 堆排序详解

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0q6qLBDQ-1720192659452)(https://i-blog.csdnimg.cn/direct/0f2c72ccbaf94cb6b82fcf98db94d75b.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pho8P4Lh-1720192659453)(https://i-blog.csdnimg.cn/direct/276d4ccb5e3648eeb46bdd8931a2563e.png)]

2.1 堆排序整体思路

1):给出待排序的数组,咱们脑补一个逻辑结构,然后将该逻辑结构整体调整为大堆或者小堆(建堆)

2): 留个问题:降序构建大堆还是小堆呢?
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wF53FEr1-1720192659453)(https://i-blog.csdnimg.cn/direct/fe41635d2ec449d5a704a324e1a82319.png)]

3):打印输出数据。

2.2 思路详解

2.2.1 建堆

以大堆为例哈:既然前面都铺垫了向下调整算法,你们肯定猜到了是通过该算法来建堆啦。

注意该算法的使用前提:要求左右子树都是大堆。怎么办呢?聪明如你们,我们从逻辑结构的后面往前面用该算法不就行啦!!

在这里插入图片描述

2.2.2 堆排序完整代码

#include <stdio.h>
//实现交换
void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
//向下调整法
void AdjustDown(int* arr, int n, int root)
{
	//双亲的下标
	int parent = root;
	//较大孩子的下标,默认为左孩子
	int child = parent * 2 + 1;
	//如果孩子的下标不越界,进入循环
	while (child < n)
	{
		//如果右孩子存在(下标没越界),并且右孩子大于左孩子,更新child
		if (child + 1 < n && arr[child + 1] > arr[child])
		{
			child = child + 1;
		}
		//如果较大的孩子大于双亲,交换
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			//改变parent的下标如果满足条件继续向下调整
			parent = child;
			child = parent * 2 + 1;
		}
		//如果较大的孩子不大于双亲,root节点的大堆构建完毕
		else
		{
			break;
		}
	}
}
void HeapSort(int* arr, int n)
{
	//循环从后面往前面对需要的数组元素使用向下调整算法
	int i = 0;
	//向下调整次数	(n-1-1)/2
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		//向下调整
		AdjustDown(arr, n, i);
	}
}

int main()
{
	//待排序的数组
	int arr[] = { 6,4,2,8,3,1,9,7,5,0 };
	//调用主体函数
	HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
	//打印数据
	PrintArray(arr, sizeof(arr) / sizeof(arr[0]));
 
	return 0;
}

                     
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63

2.2.3 输出数据

这部分比较简单,不多分析。

3. 时间复杂度分析

堆排序的时间复杂度分析,应该是排序算法中最复杂的,需要具备高中的基础知识!!!!

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/知新_RL/article/detail/792817
推荐阅读
相关标签
  

闽ICP备14008679号