c - 堆排序程序不返回结果

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[0] 交换 a[0]。最后你调用downheap(a, n, 0) 。

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

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);
    }
}

编辑

downheap的非递归实现:

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;
    }
}