c - 在c中使用sift down方法实现堆排序

Question

我正在尝试使用 c 中的向下筛选方法来实现堆排序，程序的输出缺少数组的第 0 个索引。我找不到问题所在，是否是由于数组溢出？

这是我的代码

#include<stdio.h>
void heapSort(int[], int);
void siftdown(int[], 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\n", array[i]);
        }
     return 0;
}
void heapSort(int array[], int nodeCount){
     //creating a heap
     for(int i = nodeCount / 2; i >= 1; i--){
         siftdown(array, array[i], i, nodeCount);
     }

     //perform heapsort
     for(int lastNode = nodeCount; lastNode > 1; lastNode--){
         int lastNodeValue = array[lastNode];
         array[lastNode] = array[1];
         array[1] = lastNodeValue;
         siftdown(array, lastNodeValue, 1, lastNode -1);
     }
}
void siftdown(int array[], int nodeValue, int root, int last){
     int leftChild = 2 * root + 1 ;
     while(leftChild <= last){ //at least has one child
         if(leftChild < last){ //has right child
             if(array[leftChild + 1] > array[leftChild]){
                 leftChild++;
             }
        }
         if(nodeValue >= array[leftChild]){
             break;
         }
         else{
             array[root] = array[leftChild];
             root = leftChild;
            leftChild = 2 * root + 1;
         }
         array[root] = nodeValue;
     }
}

程序的输出:

Sorted array: 5 1 2 3 4

Answer 1

heapSort 函数中的循环是:

 for(int i = nodeCount / 2; i >= 1; i--){
     siftdown(array, array[i], i, nodeCount);
 }

因为 i 永远不会为 0，所以您永远不会向下筛选该节点。将比较更改为 i >= 0。

在您的 heapSort 函数中，您有以下循环:

 //perform heapsort
 for(int lastNode = nodeCount; lastNode > 1; lastNode--){
     int lastNodeValue = array[lastNode];
     array[lastNode] = array[1];
     array[1] = lastNodeValue;
     siftdown(array, lastNodeValue, 1, lastNode -1);
 }

C 中的数组从 0 开始。因此，如果数组中有 5 个项目，则索引为 0、1、2、3、4。循环使用数组索引 1、2、3、4、5。也需要改变这个循环。它看起来像:

 //perform heapsort
 for(int lastNode = nodeCount-1; lastNode > 0; lastNode--){
     int lastNodeValue = array[lastNode];
     array[lastNode] = array[0];
     array[0] = lastNodeValue;
     siftdown(array, lastNodeValue, 0, lastNode-1);
 }