#include <stdio.h>
void temp(int &x,int &y)
{
int t;
t=x;
x=y;
y=t;
}
void Heapify(int a[],int start,int end)
{
int dad,son;
dad=(end-1)/2;
son=2*dad+1;
if(son+1<=end)
{
if(a[son]<a[son+1])
son=son+1;
}
while(dad>=0)
{
while(a[son]>a[dad])
{
temp(a[son],a[dad]);
if(son<=(end+1)/2)
{
dad=son;
son=2*dad+1;
if(son+1<=end)
{
if(a[son]<a[son+1])
son=son+1;
}
}
}
dad--;
son=2*dad+1;
if(son+1<=end)
{
if(a[son]<a[son+1])
son=son+1;
}
}
}
void HeapSort(int a[],int start,int end)
{
Heapify(a,start,end);
int i;
for(i=end;i>0;i--)
{
temp(a[0],a[i]);
Heapify(a,start,i);
}
}
int main()
{
int a[10]={3,87,2,93,78,56,61,38,12,40};
HeapSort(a,0,9);
}
![](https://profile-avatar.csdnimg.cn/default.jpg!4)
数据结构堆排序找错,求回复
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
3条回答 默认 最新
- Kwan的解忧杂货铺@新空间代码工作室 2024-06-01 18:16关注
晚上好🌙🌙🌙
本答案参考ChatGPT-3.5在你的代码中,
HeapSort
函数存在一个错误,它在每次交换最大值到末尾后没有正确地重新调用Heapify
。这会导致堆的性质破坏,影响排序结果。以下是修复后的代码:#include <stdio.h> void temp(int &x, int &y) { int t; t = x; x = y; y = t; } void Heapify(int a[], int start, int end) { int dad, son; dad = (end - 1) / 2; son = 2 * dad + 1; if (son + 1 <= end) { if (a[son] < a[son + 1]) son = son + 1; } while (dad >= 0) { while (a[son] > a[dad]) { temp(a[son], a[dad]); if (son <= (end + 1) / 2) { dad = son; son = 2 * dad + 1; if (son + 1 <= end) { if (a[son] < a[son + 1]) son = son + 1; } } } Heapify(a, start, dad); // 这里添加了对 dad 的递归调用 dad--; son = 2 * dad + 1; if (son + 1 <= end) { if (a[son] < a[son + 1]) son = son + 1; } } } void HeapSort(int a[], int start, int end) { Heapify(a, start, end); int i; for (i = end; i > 0; i--) { temp(a[0], a[i]); Heapify(a, start, i - 1); // 修改为 i - 1,因为每次下移一个元素 } } int main() { int a[10] = {3, 87, 2, 93, 78, 56, 61, 38, 12, 40}; HeapSort(a, 0, 9); return 0; }
现在,
HeapSort
函数已经修复,它会在每次交换后正确地重新构建子树,以保持堆的特性。这样,排序结果应该是正确的。解决 无用评论 打赏 举报 编辑记录
悬赏问题
- ¥200 csgo2的viewmatrix值是否还有别的获取方式
- ¥15 Stable Diffusion,用Ebsynth utility在视频选帧图重绘,第一步报错,蒙版和帧图没法生成,怎么处理啊
- ¥15 请把下列每一行代码完整地读懂并注释出来
- ¥15 pycharm运行main文件,显示没有conda环境
- ¥15 易优eyoucms关于二级栏目调用的问题
- ¥15 寻找公式识别开发,自动识别整页文档、图像公式的软件
- ¥15 为什么eclipse不能再下载了?
- ¥15 编辑cmake lists 明明写了project项目名,但是还是报错怎么回事
- ¥15 关于#计算机视觉#的问题:求一份高质量桥梁多病害数据集
- ¥15 特定网页无法访问,已排除网页问题