关于CLR中堆排序若干问题的代码实现

  本来计划在2.12之前把Hash Label的问题结束,无奈前几天贪玩,今天才把堆排序的代码写出来.

 

#include  < stdio.h > #include  < math.h > static   int  Heapsize = 10 ; int  Right( int  i) ... {return 2*i+1;} int  Left( int  i) ... { return 2*i;} int  Parent( int  i) ... { return floor(i/2);} void  MaxHeapify( int  A[], int  i) ... { int l,r,largest,var;  l=Left(i);  r=Right(i);  if ((l<=Heapsize)&&(A[l]>A[i]))     largest=l;  else largest=i;  if ((r<=Heapsize)&&(A[r]>A[largest]))     largest=r;  if (largest!=i)     ...{var=A[i];      A[i]=A[largest];      A[largest]=var;       MaxHeapify(A,largest);     }} void  BuildMaxHeap( int  A[]) ... {  int j=floor(Heapsize/2);  for(;j>=1;j--)      MaxHeapify(A,j);} void  HeapSort( int  A[]) ... { int i,var;  for(i=10;i>=2;i--)   ...{ var=A[1];     A[1]=A[i];     A[i]=var;     Heapsize--;     MaxHeapify(A,1);    }} void  main() ... { int A[11]=...{0,16,14,10,8,7,9,3,2,4,1};  int i=1;  HeapSort(A);  for(;i<=10;i++)   printf("No.%d=%d ",i,A[i]);  getch();}

   其中的MaxHeapify BuildMaxHeap HeapSort 本来是自己按书中内容分别实现的,现在归结为一个文件,遍于阅读.

通过学习,现在对递归调用有了初步的感官认识,但在深入到理论分析,例如主定理的应用和证明,以及实践当中还有很长的路要走.

  现在看到全书第二部分-排序和顺序统计学,终于结束了前段时间纯数理分析,虽然我对数学分析并不排斥,但终于能动手写代码,感觉很好.

  这次的代码虽然实现了算法及正确性,但是在组织语言上仍有待提高,特别关于Heapsize和数组下标的分配仍然需要改进.