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條件的自由。）