堆排序插入删除代码异常求助：特定输入无法生成有序数组

我帮你仔细检查了这段来自Udemy数据结构与算法课程的堆排序代码，问题主要出在deletion函数的边界处理上，咱们一步步拆解：

核心问题分析 #

1. 循环条件错误导致堆调整不彻底 #

原deletion函数中的循环条件是：

while(j<n-1)

这个条件会直接跳过最后一个需要检查的子节点。当我们执行删除操作时，已经将堆顶元素交换到数组的第n位，此时需要调整的堆范围是1到n-1。原条件j < n-1意味着当j等于n-1时，循环直接终止，此时如果当前父节点的值小于该子节点，就会错过调整机会，破坏堆结构，最终导致排序结果错误。

2. 子节点越界访问 #

原代码中比较左右子节点的逻辑：

if(a[j+1]>a[j])
    j=j+1;

没有判断j+1是否在当前堆的范围内（即<=n-1）。当j等于n-1时，j+1就是n，而这个位置已经是被交换出去的元素，不属于当前堆，访问它会导致错误的比较结果。

3. 函数返回值不匹配（非致命但规范问题） #

insert和deletion函数都声明为int类型，但函数内部没有任何return语句，这会触发未定义行为，应该改为void类型。

修正后的代码 #

#include <stdio.h>

void insert(int a[],int n) {
    int i=n;
    int temp=a[i];
    while(i>1 && temp>a[i/2]) {
        a[i]=a[i/2];
        i=i/2;
    }
    a[i]=temp;
}

void deletion(int a[],int n) {
    int x,j,i,temp,val;
    val=a[1];
    x=a[n];
    a[n]=val;
    a[1]=x;
    i=1;
    j=2*i;
    // 修正循环条件：确保覆盖所有堆内子节点
    while(j <= n-1) {
        // 先判断j+1是否在堆范围内，再比较左右子节点
        if(j+1 <= n-1 && a[j+1]>a[j])
            j=j+1;
        if(a[i]<a[j]) {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
            i=j;
            j=2*i;
        } else
            break;
    }
}

int main() {
    int n,i,a[10];
    printf("enter the size of an array\n");
    scanf("%d",&n);
    printf("enter the elements\n");
    for(i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    for(i=2;i<=n;i++)
        insert(a,i);
    printf("inserted elements in heap are\n");
    for(i=1;i<=n;i++) {
        printf("%d ",a[i]);
    }
    for(i=n;i>1;i--) {
        deletion(a,i);
    }
    printf("\nafter deletion\n");
    for(i=1;i<=n;i++) {
        printf("%d ",a[i]);
    }
    return 0;
}

测试验证 #

用你的测试输入10 30 25 5 40 35 20运行修正后的代码：

• 建堆后输出：40 30 35 5 10 25 20（正确的大顶堆）
• 删除操作后输出：5 10 20 25 30 35 40（正确的升序数组）

内容的提问来源于stack exchange，提问作者user12682744