l

成都手游码农一枚
随笔 - 32, 文章 - 0, 评论 - 117, 引用 - 0
数据加载中……

堆排序


如果有错,希望能指出,谢谢。

/*
堆排序。
*/

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

posted on 2009-11-04 16:53 l1989 阅读(319) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理