//C++程序,
//文件后缀名为.cpp,C的话,自己修改一下就OK了,输入输出部分,相信你的能力的
#include<iostream>
#include<iomanip>
using namespace std;
//显示数组元素
void Display(int* A,int length)
{
cout<<endl;
for(int
i=0;i<length;i++)
{
cout<<setw(4)<<A[i];
if((i+1)==0)
cout<<endl;
}
cout<<endl;
}
//交换两数字
void swap(int& a,int& b)
{
int temp =
b;
b = a;
a =
temp;
}
//返回父节点下标
int Parent(int i)
{
return
(i-1)/2;
}
//返回左孩子下标
int Left(int i)
{
return
2*i+1;
}
//返回右孩子下标
int Right(int i)
{
return
2*i+2;
}
//维护堆的性质
void MaxHeapAdjust(int A[],int i,int heapsize)
{
int l =
Left(i);
int r =
Right(i);
int largest
= i;
if(l<=(heapsize-1)&&A[l]>A[i])
largest = l;
if(r<=(heapsize-1)&&A[r]>A[largest])
largest = r;
if(largest!=i)
{
swap(A[i],A[largest]);
MaxHeapAdjust(A,largest,heapsize);
}
}
//建堆
void BuildHeap(int *A,int length)
{
int heapsize
= length;
for(int
i=int(length/2);i>-1;i--)
MaxHeapAdjust(A,i,heapsize);
}
//堆排序
void HeapSort(int A[],int length)
{
//堆建立后A[0]是最大值
BuildHeap(A,length);
int heapsize
= length;
for(int
i=length-1;i>0;i--)
{
swap(A[i],A[0]);
heapsize = heapsize - 1;
MaxHeapAdjust(A,0,heapsize);
}
}
int main()
{
int
*A;
int
count;
cout<<"请输入元素的个数: ";
cin>>count;
A = new
int[count];
cout<<"请输入元素:
"<<endl;
for(int
i=0;i<count;i++)
cin>>A[i];
cout<<"\n\t\t排序前..."<<endl;
Display(A,count);
HeapSort(A,count);
cout<<"\n\t\t排序后..."<<endl;
Display(A,count);
return
0;
}
温馨提示:答案为网友推荐,仅供参考