堆排序法

堆排序法，就是通过堆这种数据结构来实现排序，算法复杂度为O(nlogn)。

堆是一种完全二叉树且所有的父节点均大于（或小于）其子节点。

堆排序就是将所有待排序的元素组成一个堆，然后不断d出堆顶的元素并调用函数维持堆序，直扒拆到所有元素均被d出后，排序完成。被d出的元素序列即一个有序数列。

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

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

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

以下是春贺枣我自己写的一个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=0i<ni++)

{

cin>>a

Insert(a)

}

for(i=0i<ni++)

cout<<Pop()<<' '

system("pause")

return 0

}

初始堆： 49 a[1] 38 65 a[2]a[3] 97 76 13 27 a[4] a[5] a[6] a[7] 50 a[8]procedure heap(nn,ii:integer) var x,i,j:integer begin i:=iix:=a[ii]j:=2*iiwhile j<=nn dobeginif (j<nn) and(a[j]<a[j+1] then j:=j+1 if x<a[j] then begin a[i]:=a[j]i:=jj:=2*iendelse j:=nn+1 end end主程序：for i:=n div 2 downto 1 do heap(n,i) /heap相当于搜索顶点i的所有子念模搜节点，找出最大的和它替换for i:=n downto 2 do begintemp:=a[1]a[1]:=a[i]a[i]:=temp/将当前最大的数（放在a[1]）和第i个数交换，仔历保证从后面往前数是heap(i-1,1) 从大到小，则程序完成时，数组a从前往后是从小到码携大 end至于过程自己用笔算，很快就会明白，不明白算了就明白。

---