2

我正在尝试实现 Cormen 中提供的堆排序算法。我的代码如下：

    #include<stdio.h>
    #include<conio.h>
    void max_heapify(int *,int);
    void build_max_heap(int *,int);
    void heapsort(int *,int);
    void swap(int,int);
    int heapsize;
    int main()
    {
            int *arr,n,i;
            printf("Enter no. of elements = ");
            scanf("%d",&n);
            arr=(int *)malloc(sizeof(int)*n);
            for(i=0;i<n;i++)
            {
             printf("Enter array elements = ");
             scanf("%d",&arr[i]);
            }
            //heapsize = n;
            heapsort(arr,n);
            printf("\nAfter heapsort \n");
            for(i=0;i<n;i++)
            {
                printf("%d  ",arr[i]);
            }
        return 0;
    }
 void heapsort(int *arr,int len)
 {
   int i;
   build_max_heap(arr,len);
    for(i= len-1;i>=1;i--)
    {
        swap(&arr[0],&arr[i]);
        heapsize = heapsize -1;
        max_heapify(arr,0);
    }
 }
void max_heapify(int *arr,int i)
{
    int l=2*i,r=2*i+1,largest;
    if(l<heapsize && arr[l]>arr[i])
        largest = l;
    else
        largest = i;
    if(r<heapsize && arr[r]>arr[largest])
        largest = r;

    if(largest != i)
    {
        swap(&arr[i],&arr[largest]);
        max_heapify(arr,largest);
    }
     }
void build_max_heap(int *arr,int len)
{
    heapsize = len;
    int i;
    for(i =len/2;i>=0;i--)
    {
        max_heapify(arr,i);
    }
}
void swap(int *a ,int *b)
{
    int temp = *a;
    *a= *b;
    *b= temp;
}

我无法弄清楚我的代码到底出了什么问题。数组未排序。事实上，原始数组正在打印。我哪里错了？

4

4 回答 4

5

您swap的函数按值获取参数。因此，原始值被复制并交换副本而不是原始值。

swap( int *a, int *b)
于 2013-08-12T07:49:11.980 回答
2

1）修复交换，你是按价值传递的。这意味着在调用交换之后没有任何改变！

2) max_heapify 函数错误。您的左右子计算值相差 1。交换时，您将索引与数组值交换，哎呀。

3）堆排序for循环是错误的。您应该将第一个元素（堆中的最大元素）放在当前堆的最后一个索引中，减小堆的大小，使最后一个元素成为排序列表的一部分，而不是堆。然后你从根向下渗透，而不是从最后一个元素。应该：

 for(i= len-1;i>=1;i--)
   {
    swap(arr[0],arr[i]);
    heapsize = heapsize -1;
    max_heapify(arr,0);
   }
于 2013-08-12T08:45:07.190 回答
1

您观察到您的数组根本没有排序。尝试逐步完成完整的堆排序。因此，作为一种调试技术，创建此代码的副本并将堆排序替换为冒泡排序。（冒泡排序更容易编码）。让冒泡排序工作，这包括传递参数并在排序前后打印数组。

然后进行堆排序。

于 2013-08-12T07:50:19.670 回答
1

Cormen 中列出的算法似乎有错误。只需更改代码中的以下行：

max_heapify(arr,0); \在堆排序函数中

和

build_max_heap(arr,heapsize);

于 2013-08-30T20:30:01.517 回答