|
|
如果有错，希望能指出，谢谢。
  /**//*
 堆排序。
 */
 #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);
}
|