C语言基于下沉法实现堆排序：输出缺失数组第0元素排查求助

嘿，我来帮你排查这个堆排序的问题！你提到用下沉法实现堆排序时，输出缺失了数组的第0个元素，还怀疑是数组溢出导致的。结合你给出的代码片段，我大概率能猜到问题出在索引处理不一致上——很多堆排序的教程会用1-based索引（把数组的第1个元素作为堆的根节点），但你的主函数是按0-based来遍历输出的，这就会导致第0个元素被忽略掉。

核心问题分析 #

如果你的heapSort或siftdown函数是按1-based逻辑写的（比如根节点在索引1，左孩子是2*i，右孩子是2*i+1），那数组的第0个元素根本没被纳入堆的构建和排序流程里，输出时自然就看不到它了。而数组溢出通常会导致程序崩溃或输出乱码，和你“缺失元素”的症状不太匹配，不过我们也可以在修正时顺便排查边界问题。

修正后的0-based堆排序代码 #

我给你写了一个完整的、基于0-based索引的下沉法堆排序实现，完美适配你的主函数遍历逻辑：

#include<stdio.h>

void heapSort(int[], int);
void siftdown(int[], int, int);

int main(void) {
    int array[] = {5, 2, 1, 4, 3};
    int nodeCount = sizeof(array)/sizeof(array[0]);
    
    heapSort(array, nodeCount);
    
    printf("Sorted array:\n");
    for(int i=0; i < nodeCount; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

void heapSort(int arr[], int n) {
    // 从最后一个非叶子节点开始，构建最大堆
    for (int i = n/2 - 1; i >= 0; i--) {
        siftdown(arr, n, i);
    }
    
    // 逐个取出堆顶元素，放到数组末尾
    for (int i = n-1; i >= 0; i--) {
        // 交换堆顶（当前最大元素）和未排序部分的最后一个元素
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        
        // 对剩下的未排序元素进行下沉调整
        siftdown(arr, i, 0);
    }
}

void siftdown(int arr[], int n, int root) {
    int largest = root; // 初始化最大元素为根节点
    int left = 2*root + 1; // 0-based下的左孩子索引
    int right = 2*root + 2; // 0-based下的右孩子索引
    
    // 找到左孩子、右孩子、根节点中的最大值
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    
    // 如果最大值不是根节点，交换并递归调整子堆
    if (largest != root) {
        int temp = arr[root];
        arr[root] = arr[largest];
        arr[largest] = temp;
        
        siftdown(arr, n, largest);
    }
}

关键修正点 #

1. 0-based索引适配：
   • 非叶子节点从n/2 - 1开始（最后一个叶子节点的父节点索引是(n-1-1)/2 = n/2 -1），确保第0个元素被纳入堆构建。
   • 左孩子索引改为2*root +1，右孩子改为2*root +2，符合0-based的计算逻辑。
2. 边界检查：
   • 在siftdown里添加left < n和right < n的判断，避免数组越界访问（这也解决了你对溢出的担忧）。
3. 排序流程对齐：
   • 堆排序时，每次把堆顶（索引0）和未排序部分的最后一个元素交换，然后调整堆的大小为i（因为末尾元素已经有序）。

验证结果 #

运行上面的代码，输出会是：

Sorted array:
1 2 3 4 5 

所有元素都被正确排序并输出，包括原来缺失的第0个元素。

内容的提问来源于stack exchange，提问作者Sanjeet Pal Singh