学步园

根据《算法导论》第六章，写了heapsort的代码，如下：

// HeapSort.cpp : Defines the entry point for the console application.<br /> //</p> <p>#include "stdafx.h"<br /> #include <iostream><br /> #include <fstream><br /> #include <math.h><br /> using namespace std;</p> <p>#define N 1000</p> <p>void HeapSort(int *a, int &heapsizeA);<br /> void BuildMaxHeap(int *a, int heapsizeC);<br /> void MaxHeapify(int *a,int i, int &heapsizeB);</p> <p>int main(int argc, char* argv[])<br /> {<br /> int n;<br /> int a[N];<br /> int heapsize;<br /> ifstream fin("HeapSortData.123");//可以自定义各种奇怪的扩展名<br /> ofstream fout("HeapSortData.out");<br /> if(!fin)<br /> { cout<<"输入数据文件打开失败/n";<br /> exit(1);<br /> }<br /> fin>>n;//回车换行或者空格都是fstream的分隔符<br /> cout<<"The array is : /n";<br /> //a[0]=1000;<br /> for( int k=1 ; k<=n ; k++ )//为了和原书一致，数组从a[1]~a[n]存储数据，而弃掉a[0]。是否定义a[0]并不影响程序<br /> {<br /> fin>>a[k];<br /> cout<<a[k]<<'/t';<br /> }<br /> fin.close();<br /> heapsize=n;//n编译时不能确定，运行时才能确定。尽管heapsize的值是n,但是也是合理的。<br /> HeapSort(a,heapsize);<br /> if(!fout)<br /> { cout<<"输出数据文件创建失败/n";<br /> exit(1);<br /> }<br /> for( int i=1 ; i<=n ; i++ )<br /> {<br /> cout<<a[i]<<'/t';<br /> fout<<a[i]<<'/t';<br /> }<br /> return 0;<br /> }</p> <p>void HeapSort(int *a, int &heapsizeA)<br /> {<br /> BuildMaxHeap(a,heapsizeA);<br /> for(int i=heapsizeA;i>=2;i--)<br /> {<br /> int temp=a[i];<br /> a[i]=a[1];<br /> a[1]=temp;<br /> heapsizeA--;<br /> MaxHeapify(a,1,heapsizeA);<br /> }<br /> }</p> <p>void BuildMaxHeap(int *a, int heapsizeC){<br /> for(int i=floor(heapsizeC/2);i>=1;i--)<br /> MaxHeapify(a,i,heapsizeC);<br /> }</p> <p>void MaxHeapify(int *a,int i, int &heapsizeB){//引用型变量的使用<br /> int l=2*i;<br /> int r=2*i+1;<br /> int largest;<br /> if((l<=heapsizeB)&&(a[i]<a[l]))<br /> largest=l;<br /> else<br /> largest=i;<br /> if((r<=heapsizeB)&&(a[largest]<a[r]))<br /> largest=r;<br /> if(largest!=i)<br /> {<br /> int temp=a[largest];<br /> a[largest]=a[i];<br /> a[i]=temp;<br /> MaxHeapify(a,largest,heapsizeB);<br /> }</p> <p>}</p> <p>