c - 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 不应该是连续的，它们应该是嵌套的。否则，您将在 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 条件。)