谁能给我详细讲下堆排序?(PAS
因为只能上传一个文件,我把几个图弄到一起了,前两个图是堆示范,后面5个是建堆示范
1。 基本思想:
堆排序是一树形选择排序,在排序过程中,将R[1。。N]看成是一颗完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
2。 堆的定义: N个元素的序列K1,K2,K3,。。。,Kn。称为堆,当且仅当该序列满足特性:
Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])
堆实质上是满足如下性质的完全二叉树:树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。 例如序列10,15,56,25,30,70就是一个堆,它对应的完全二叉树如上图所...全部
因为只能上传一个文件,我把几个图弄到一起了,前两个图是堆示范,后面5个是建堆示范
1。 基本思想:
堆排序是一树形选择排序,在排序过程中,将R[1。。N]看成是一颗完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
2。 堆的定义: N个元素的序列K1,K2,K3,。。。,Kn。称为堆,当且仅当该序列满足特性:
Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])
堆实质上是满足如下性质的完全二叉树:树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。
例如序列10,15,56,25,30,70就是一个堆,它对应的完全二叉树如上图所示。这种堆中根结点(称为堆顶)的关键字最小,我们把它称为小根堆。反之,若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字,则称之为大根堆。
3。 排序过程:
堆排序正是利用小根堆(或大根堆)来选取当前无序区中关键字小(或最大)的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是:将当前无序区调整为一个大根堆,选取关键字最大的堆顶记录,将它和无序区中的最后一个记录交换。
这样,正好和直接选择排序相反,有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。
【示例】:对关键字序列42,13,91,23,24,16,05,88建堆
Procedure Sift(Var R :FileType; I, M : Integer);
//在数组R[I。
。M]中调用R[I],使得以它为完全二叉树构成堆。事先已知其左、右子树(2I+1 <=M时)均是堆//
Begin
X := R[I]; J := 2*I; //若J <=M, R[J]是R[I]的左孩子//
While J <= M Do //若当前被调整结点R[I]有左孩子R[J]//
begin
If (J < M) And R[J]。
Key < R[J+1]。Key Then
J := J + 1 //令J指向关键字较大的右孩子//
//J指向R[I]的左、右孩子中关键字较大者//
If X。
Key < R[J]。Key Then //孩子结点关键字较大//
begin
R[I] := R[J]; //将R[J]换到双亲位置上//
I := J ; J := 2*I //继续以R[J]为当前被调整结点往下层调整//
end;
Else
Exit//调整完毕,退出循环//
end
R[I] := X;//将最初被调整的结点放入正确位置//
End;//Sift//
Procedure HeapSort(Var R : FileType); //对R[1。
。N]进行堆排序//
Begin
For I := N Div Downto 1 Do //建立初始堆//
Sift(R, I , N)
For I := N Downto 2 do //进行N-1趟排序//
begin
T := R[1]; R[1] := R[I]; R[I] := T;//将当前堆顶记录和堆中最后一个记录交换//
Sift(R, 1, I-1) //将R[1。
。I-1]重成堆//
end
End; //HeapSort//
。收起