念心卓

用户名：uq_80412005216

访问量：2757

签　名：

人不自渡，天也难助

等　　级
排　　名	1585
经　　验	2766
参赛次数	2
文章发表	24
年　　龄	0
在职情况	学生
学　　校	哔哩哔哩大学
专　　业	软件工程

　　自我简介：

TA的其他文章

链表的基本操作（C语言版）
浏览：88

链表的删除练习(C语言版)
浏览：318

双向循环链表(C语言版)
浏览：69

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

堆排序(C语言)

　　作者: 念心卓　　　　发表时间：2022-09-18 17:04:11 浏览：143　|　评论：0　

原题链接：数据结构-堆排序

```
#include <stdio.h>
#include <stdlib.h>

//调整堆
void HeadAdjust(int* arr, int k, int len) {
	arr[0] = arr[k];//暂存子树的根结点
	for (int i = 2*k; i <= len; i *= 2)//指向左孩子,沿key较大的子节点向下筛选("下坠")
	{
		if (i < len && arr[i] < arr[i+1])//只有i<len的时候才能保证有右孩子，此时判断左右孩子更大
		{
			i++;//取较大的key的下标
		}
		if (arr[0] >= arr[i])//表示当前根就是最大的，无须进行后序操作
		{
			break;
		}
		else
		{
			arr[k] = arr[i];//将arr[i]调整到双亲结点上
			k = i;//修改K的值继续向下筛选("下坠")
		}
	}
	arr[k] = arr[0];//被筛选的结点放入最终位置
}

//建立大根堆
void BuildMaxHeap(int* arr, int len) {
	//建立大根堆时，只需要调整所有非叶子结点(i <= n/2)
	for (int i = len/2; i > 0; i--)//从[n/2,1]反复调整堆
	{
		//对小元素不断"下坠"
		HeadAdjust(arr, i, len);
	}
}

//堆排序
void HeapSort(int* arr, int len) {
	//因为是升序，所以建立大根堆
	BuildMaxHeap(arr, len);
	for (int i = len; i > 0; i--)
	{
		//第一个元素和堆底元素进行交换
		int temp = arr[i];
		arr[i] = arr[1];
		arr[1] = temp;
		HeadAdjust(arr, 1, i - 1);//调整，把剩余的i-1个元素整理成堆
	}
}
int main() {

int n;
	scanf("%d", &n);
	int* arr = (int*)malloc(sizeof(int) * (n+1));
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &arr[i]);//下标为0的位置暂时不存，后序会使用到
	}
	HeapSort(arr, n);
	for (int i = 1; i <= n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;

}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

念心卓

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

去掉双斜杠注释（C语言代码）

C二级辅导-进制转换（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

堆排序(C语言)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

永远的丰碑（C语言代码）

简单的a+b （C语言代码）

矩阵转置（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

明明的随机数（C语言代码）

C语言训练-最大数问题（C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

念心卓

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

去掉双斜杠注释 （C语言代码）

C二级辅导-进制转换 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

堆排序(C语言)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

永远的丰碑 （C语言代码）

简单的a+b （C语言代码）

矩阵转置 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

明明的随机数 （C语言代码）

C语言训练-最大数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

去掉双斜杠注释（C语言代码）

C二级辅导-进制转换（C语言代码）

　　评论区

永远的丰碑（C语言代码）

矩阵转置（C语言代码）

明明的随机数（C语言代码）

C语言训练-最大数问题（C语言代码）