|
|
如果有錯，希望能指出，謝謝。
  /**//*
 堆排序。
 */
 #include <iostream>
using namespace std;
/**//*交換元素*/
template<typename _Ty>
inline void Swap(_Ty& _f,_Ty& _s)
 {
_Ty _t=_f;
_f=_s;_s=_t;
}
/**//*調整堆*/
template<typename _Ty>
void HeapAdjust(_Ty* _arr,int _beg,int _end)
{//_beg _end 第_beg個元素到第_end個元素 由1開始
for(int i=_beg*2;i<=_end;i*=2)
  {
//索引由1開始 使用時-1
if(i+1<=_end&&_arr[i-1]<_arr[i])++i;//左右結點元素相比較
if(_arr[i-1]>_arr[i/2-1]) //大于父親結點則交換
Swap(_arr[i-1],_arr[i/2-1]);
else
return;
 }
}
/**//*堆排序*/
template<typename _Ty>
void HeapSort(_Ty* _arr,int _size)
{
//將數組調整成堆
for(int i=_size/2;i>0;--i)
HeapAdjust(_arr,i,_size);
//取堆頂和最后一個元素交換
for(int j=_size;j>1;--j)
{
Swap(_arr[0],_arr[j-1]);
HeapAdjust(_arr,1,j-1);
}
}
/**//*打印數組*/
template<typename _Ty>
void OutArr(_Ty* _arr,int _size,ostream& _Os=cout)
{
for(int i=0;i<_size;++i)
_Os<<_arr[i]<<" ";
_Os<<endl;
}
int main()
{
int arr[100];
for(int i=0;i<100;arr[i++]=rand()%100);
OutArr(arr,100);
cout<<endl;
HeapSort(arr,100);
OutArr(arr,100);
}
|