Question

堆排序法

请高人讲解一下堆排序法到底是怎么排的，属于计算机二级的中的排序问题，能不能附加例题呢

Answer 1

堆排序法，就是通过堆这种数据结构来实现排序，算法复杂度为O(nlogn)。
堆是一种完全二叉树且所有的父节点均大于（或小于）其子节点。
堆排序就是将所有待排序的元素组成一个堆，然后不断弹出堆顶的元素并调用函数维持堆序，直到所有元素均被弹出后，排序完成。被弹出的元素序列即一个有序数列。

维持堆序的一般做法是这样：

当一个节点被插入时，将该节点放在堆的末尾（这是为了保证堆是完全二叉树）然后将该节点与它的父节点比较，看该节点是否大于（或小于）其父节点，即判断当前的堆是否满足堆序。如果不满足，则将该节点与其父节点交换。再将该节点与其新的父节点做比较，依此类推，直到该节点不再需要与其父节点交换为止。（即满足堆序时停止）

当一个根节点被弹出（即被从堆中删除）时，将堆最尾部的节点移动到头结点的位置，然后将该节点不断与其子节点比较，如果不符合堆序则交换，直到符合堆序为止。

以下是我自己写的一个C++的堆排序的程序，希望对你理解该算法有帮助。

#include<iostream>
using namespace std;
int heap[10000],size;
void Percup(int s)
{
if(s==1)
return ;
if(heap[s/2]<heap[s])
{
swap(heap[s/2],heap[s]);
Percup(s/2);
}
}
void Percdown(int s)
{
if(s*2+1<=size&&heap[s*2+1]>heap[s])
{
swap(heap[s*2+1],heap[s]);
Percdown(s*2+1);
}
if(s*2<=size&&heap[s*2]>heap[s])
{
swap(heap[s*2],heap[s]);
Percdown(s*2);
}
}
void Insert(int k)
{
heap[++size]=k;
Percup(size);
}
int Pop()
{
int h=heap[1];
heap[1]=heap[size--];
Percdown(1);
return h;
}
int main()
{
int a,n,i;
cin>>n;
for(i=0;i<n;i++)
{
cin>>a;
Insert(a);
}
for(i=0;i<n;i++)
cout<<Pop()<<' ';
system("pause");
return 0;
}

Answer 2

堆排序法，就是通过堆这种数据结构来实现排序，算法复杂度为O(nlogn)。
堆是一种完全二叉树且所有的父节点均大于（或小于）其子节点。
堆排序就是将所有待排序的元素组成一个堆，然后不断弹出堆顶的元素并调用函数维持堆序，直到所有元素均被弹出后，排序完成。被弹出的元素序列即一个有序数列。
维持堆序的一般做法是这样：
当一个节点被插入时，将该节点放在堆的末尾（这是为了保证堆是完全二叉树）然后将该节点与它的父节点比较，看该节点是否大于（或小于）其父节点，即判断当前的堆是否满足堆序。如果不满足，则将该节点与其父节点交换。再将该节点与其新的父节点做比较，依此类推，直到该节点不再需要与其父节点交换为止。（即满足堆序时停止）
当一个根节点被弹出（即被从堆中删除）时，将堆最尾部的节点移动到头结点的位置，然后将该节点不断与其子节点比较，如果不符合堆序则交换，直到符合堆序为止。
以下是我自己写的一个C++的堆排序的程序，希望对你理解该算法有帮助。
#include<iostream>
using
namespace
std;
int
heap[10000],size;
void
Percup(int
s)
{
if(s==1)
return
;
if(heap[s/2]<heap[s])
{
swap(heap[s/2],heap[s]);
Percup(s/2);
}
}
void
Percdown(int
s)
{
if(s*2+1<=size&&heap[s*2+1]>heap[s])
{
swap(heap[s*2+1],heap[s]);
Percdown(s*2+1);
}
if(s*2<=size&&heap[s*2]>heap[s])
{
swap(heap[s*2],heap[s]);
Percdown(s*2);
}
}
void
Insert(int
k)
{
heap[++size]=k;
Percup(size);
}
int
Pop()
{
int
h=heap[1];
heap[1]=heap[size--];
Percdown(1);
return
h;
}
int
main()
{
int
a,n,i;
cin>>n;
for(i=0;i<n;i++)
{
cin>>a;
Insert(a);
}
for(i=0;i<n;i++)
cout<<Pop()<<'
';
system("pause");
return
0;
}