堆排序算法 (一)

[cpp]
/*
Name:
Copyright:
Author:
Date: 18-06-11 20:51
Description: 实现堆排序的模版类 ,元素从1开始计.T为要排序的元素类型，
[note:]必须支持 <= 运算 和 赋值运算
*/
#include
#include
using namespace std;

template
class heap
{
public:
typedef unsigned UINT;
// n 代表要排序的n个元素，要分配n+1个空间，元素位置从1开始计
heap(const UINT n)
{
_count = n;
_pA = new T[n + 1];
}
~heap()
{
_count = 0;
if(_pA)
{
delete[] _pA;
_pA = NULL;
}
}
void heapsort();
private:
void maxheap_shift(const UINT i,const UINT size);
void buildheap();
public:
T *_pA;
private:
UINT _count;
};
template
void heap::maxheap_shift(const UINT i,const UINT size)
{
UINT j=2*i;
if(j <= size)
{
if(_pA[j] <= _pA[i])
j=i;
if(2*i+1<=size)
{
if(_pA[j] < _pA[2*i+1])
j=2*i+1;
}
}
else
{
return;
}
if(j!=i)
{
T temp;
temp = _pA[i];
_pA[i] = _pA[j];
_pA[j] = temp;
maxheap_shift(j,size);
}
}

template
void heap::buildheap()
{
for(UINT i= _count/2 ;i >= 1;--i)
{
maxheap_shift(i,_count);
}
}
template
void heap::heapsort()
{
buildheap();
T tem;
for(UINT i = _count;i > 1;--i)
{
tem = _pA[1];
_pA[1] = _pA[i];
_pA[i] = tem;
maxheap_shift(1,i-1);
}
}
int main()
{
//count 表示要排序的元素个数
heap::UINT count = 30;
heap::UINT i;

heap myheap(count);
if(!myheap._pA)
{
cout<<"分配失败"< goto RETURN;
}

for(i=1;i<=count;++i)
{
myheap._pA[i] = (double)(count-i) - 0.2;
}
for(i=1;i<=count;++i)
{
cout< }
cout<<'\n';

myheap.heapsort();
for(i=1;i<=count;++i)
{
cout< }

RETURN:
system("pause");
return 0;
}

/*
Name:
Copyright:
Author:
Date: 18-06-11 20:51
Description: 实现堆排序的模版类 ,元素从1开始计.T为要排序的元素类型，
[note:]必须支持 <= 运算 和 赋值运算
*/
#include
#include
using namespace std;

template
class heap
{
public:
typedef unsigned UINT;
// n 代表要排序的n个元素，要分配n+1个空间，元素位置从1开始计
heap(const UINT n)
{
_count = n;
_pA = new T[n + 1];
}
~heap()
{
_count = 0;
if(_pA)
{
delete[] _pA;
_pA = NULL;
}
}
void heapsort();
private:
void maxheap_shift(const UINT i,const UINT size);
void buildheap();
public:
T *_pA;
private:
UINT _count;
};
template
void heap::maxheap_shift(const UINT i,const UINT size)
{
UINT j=2*i;
if(j <= size)
{
if(_pA[j] <= _pA[i])
j=i;
if(2*i+1<=size)
{
if(_pA[j] < _pA[2*i+1])
j=2*i+1;
}
}
else
{
return;
}
if(j!=i)
{
T temp;
temp = _pA[i];
_pA[i] = _pA[j];
_pA[j] = temp;
maxheap_shift(j,size);
}
}

template
void heap::buildheap()
{
for(UINT i= _count/2 ;i >= 1;--i)
{
maxheap_shift(i,_count);
}
}
template
void heap::heapsort()
{
buildheap();
T tem;
for(UINT i = _count;i > 1;--i)
{
tem = _pA[1];
_pA[1] = _pA[i];
_pA[i] = tem;
maxheap_shift(1,i-1);
}
}
int main()
{
//count 表示要排序的元素个数
heap::UINT count = 30;
heap::UINT i;

heap myheap(count);