C中的这种堆排序实现有什么问题？

Question

我一直在尝试在C的堆排序算法的实现中发现错误，但我无法找到它。它正在编译好，但是当我执行程序时，它会给出错误。

#include<stdio.h> 
int cmp(int *a, int *b){return *a-*b;} 
void swap(int *a, int *b){ 
int temp; 
temp=*a; *a=*b; *b=temp;} 
void sift_down(int *A,int parent, int n){ 
     int child; 
     if((child=2*parent+1)<n){ 
       if(child+1<n && cmp(A+child,A+child+1)<0){ 
         child++; 
       }} 
     if(cmp(A+parent,A+child)<0){ 
       swap(A+parent,A+child); 
       sift_down(A,child,n); 
     }} 
void build_heap(int A[], int n){ 
     int i; 
     for(i=(n/2)-1;i>=0;i--){ 
       sift_down(A,i,n); 
     } 
} 
void heapsort(int A[], int n){ 
     int active; 
     build_heap(A,n); 
     for(active=n-1;active>0;active--){ 
       swap(A,A+active); 
       sift_down(A,0,active); 
     } 
} 
int main(){ 
     int A[]={13,16,14,10,15,17,18,30,25},i,n; 
     n=sizeof(A)/sizeof(A[0]); 
     heapsort(A,n); 
     for(i=0;i<n;i++){ 
       printf("%d\t",A[i]); 
     } 
} 

Answer 1

有趣的支撑风格。解开，你的函数sift_down看起来是这样的：

void sift_down(int *A, int parent, int n) 
{ 
    int child; 

    if ((child = 2 * parent + 1) < n) { 
     if (child + 1 < n && cmp(A + child, A + child + 1) < 0) { 
      child++; 
     } 
    } 

    if (cmp(A + parent, A + child) < 0) { 
     swap(A + parent, A + child); 
     sift_down(A, child, n); 
    } 
} 

的if不是应该consecuteve，他们应该被嵌套。否则，您将在cmp和swap函数 - 分段错误之后访问数组末尾的child。

所以你的函数应该是这样的：

void sift_down(int *A, int parent, int n) 
{ 
    int child = 2 * parent + 1; 

    if (child < n) { 
     if (child + 1 < n && cmp(A + child, A + child + 1) < 0) { 
      child++; 
     } 

     if (cmp(A + parent, A + child) < 0) { 
      swap(A + parent, A + child); 
      sift_down(A, child, n); 
     } 
    } 
} 

（我也带到分配移动到child出if条件的自由。）