Heapsort程序不返回结果。

Question

我正在用C语言实现Heapsort程序，它与二叉树排序。当我运行这个程序时，在它满足程序中的heapsort函数之前，它是可以的。我也试着调试这一点，但是它在满足heapsort函数时仍然会出错。

在互联网上引用一些算法时，我发现它与我的源代码相似，但它们运行正常，所以我很难找到源代码中的错误

#include <stdio.h>
#define MAX 2100
void downheap(int a[], int n, int k)
{
    int i=0;
    int temp = a[0];
    while (k <= n/2)
    {
        i = k + k;
        if(i<n && a[i] <= a[i+1]) i++;
        if(temp < a[i]) break;
        a[k] = a[i]; k = i;
    }
    a[k] = temp;
}
void heapsort(int a[], int n)
{
    int i, j;
    for(i=0; i<=n; i++) downheap(a, n, i);
    while(n>=0)
    {
        j = a[0]; a[0] = a[n]; a[n] = j;
        downheap(a, --n, 0);
    }
}

int main()
{
    int n, a[MAX], i;
    printf("Enter your number of elements: ");
    scanf("%d", &n);
    for(i=0; i<n; i++) printf("%d: ", i), scanf("%d", &a[i]);
    heapsort(a, n-1);
    for(i=0; i<n; i++) printf("%d ", a[i]);
    return 0;
}

Answer 1

您的代码中有多个问题，我在下面列出：

您应该坚持通常的惯例，即n是元素的数量。在您的代码中，不方便的是元素数减去一个元素。在这种情况下，您可以调用heapsort(a, n)。

在heapsort函数中，for(i=0; i<=n; i++) downheap(a, n, i)应该是for(i=n/2-1; i>=0; i--) downheap(a, n, i)。

接下来，由于n是a中的元素数，所以循环应该是while(--n > 0)。n=0的迭代是没有意义的，因为它会将a与a交换，最后调用downheap(a, n, 0)。

函数downheap是您遇到最大问题的地方。该函数应将索引i处的元素与其两个子元素进行比较，并将树的最大值存储在索引i处。如果发生了与子元素的交换，则继续与该子元素进行交换。你的功能完全错了。这是一个正确的实现。

void downheap(int *a, int n, int k){
    int l = 2*k+1, r = 2*k+2, max = k;
    if (l < n && a[l] > a[max])
        max = l;
    if (r < n &d a[r] > a[max])
        max = r;
    if (max != k) {
        int j = a[k]; a[k] = a[max]; a[max] = j;
        downheap(a, n, max);
    }
}

正如您所看到的，这段代码与您的代码非常不同，这是完全错误的。

为了您的方便，下面是heapsort函数的代码。这段代码没有那么糟糕，但还是不正确。

void heapsort(int *a, int n){
    int i, j;
    for(i=n/2-1; i>=0; i--)
        downheap(a, n, i);
    while(--n > 0){
        j = a[0]; a[0] = a[n]; a[n] = j;
        downheap(a, n, 0);
    }
}

编辑

下堆的非递归实现：

void downheap(int *a, int n, int k){
    while (1) {
        int l = 2*k+1, r = 2*k+2, max = k;
        if (l < n && a[l] > a[max])
            max = l;
        if (r < n &d a[r] > a[max])
            max = r;
        if (max == k)
            break;
        int j = a[k]; a[k] = a[max]; a[max] = j;
        k = max;
    }
}