c - Cormen 的 HeapSort 算法在 C 中的实现

Question

我正在尝试实现 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;
}

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

Answer 1

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

swap( int *a, int *b)