Cormen's HeapSort算法的執行C

我正在嘗試實現Cormen中提供的堆排序算法。我的代碼如下：Cormen's HeapSort算法的執行C

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

我找不出在我的代碼中究竟出了什麼問題。該數組未被排序。實際上原始數組正在打印。我哪裏錯了？

來源

2013-08-12 Daggerhunt

你的'swap'是完全錯誤的（指針！），並且你用'max_heapify'中的數組值替換了一個索引，這沒有多大意義。 – Nbr44

是的..改變了，它的工作正常..我也編輯了代碼[與建議的更改] – Daggerhunt

1）修復掉，你正在通過價值。這意味着交換之後被稱爲沒有改變！

2）max_heapify函數是錯誤的。您的左右兒童計算結果偏離1.當您交換時，您將使用數組值交換索引，即yikes。

3）heapsort for-loop是錯誤的。您應該將第一個元素（堆中最大的元素）放到當前堆的最後一個索引處，減小堆的大小以使最後一個元素成爲排序列表的一部分而不是堆。然後你從根開始，而不是從最後一個元素開始。應該是：

for(i= len-1;i>=1;i--) 
    { 
    swap(arr[0],arr[i]); 
    heapsize = heapsize -1; 
    max_heapify(arr,0); 
    }

來源

2013-08-12 08:45:07 bunnybare

是的...做了更改，它的工作..我正在編輯我的文章與正確的代碼。 – Daggerhunt

您的swap函數按值取值。因此，原始值被複制並且副本被交換而不是原件。

swap(int *a, int *b)

來源

2013-08-12 07:49:11

你注意到你的數組根本沒有被排序。嘗試按增量進行完整的堆排序。因此，作爲一種調試技術，創建此代碼的副本並用冒泡排序替換堆排序。（冒泡排序更容易編碼）。讓冒泡排序工作，這包括傳遞參數並在排序前後打印數組。

然後做堆排序。

來源

2013-08-12 07:50:19 JackCColeman

Cormen中列出的算法似乎有錯誤。只需更改代碼中的以下行：

max_heapify（arr，0）; \在堆排序功能

與

build_max_heap（ARR，堆大小）;

來源

2013-08-30 20:30:01

Cormen's HeapSort算法的執行C

回答

相關問題