|
EDA365欢迎您登录!
您需要 登录 才可以下载或查看,没有帐号?注册
x
《算法导论(第三版)》第六章,堆排序0 u7 p* A5 Z2 P Q s2 n
+ U n3 B/ p1 m8 e8 ]8 d$ V4 ^1 s; k
matlab使用堆比较麻烦,且不好理解,就直接使用堆排序的思想,直接操作数组进行示意,简化代码。
- C6 C G( S# `9 \
5 g3 V7 a( r$ Z c7 C; DHEAPSORT
0 d$ x' ^4 R2 `! x6 f- clear;clc
- A=[16 14 10 8 7 9 3 2 4 1]%数组
- %A=[4 1 3 2 16 9 10 14 8 7]%数组
- A=BUILD_MAX_HEAP(A);%建最大堆
- for i=length(A):-1:1%反方向引导退出
- temp(i)=A(1);
- A(1)=A(i);
- A(i)=[];
- A=MAX_HEAPIFY(A,1);
- end
- A=temp%结果* |" }2 f" g' ~% w" P
0 a# Y% \3 a, s1 m' W& b
$ }, P& J! ~/ i6 L: m
M$ ^ i9 I2 X; D建立堆
* e6 \# @6 n3 _$ J- function [A] = BUILD_MAX_HEAP(A)
- for i=floor(length(A)/2):-1:1
- A=MAX_HEAPIFY(A,i);
- end
- end/ z J" f: B3 N( v; }3 E2 k
! I( |, r0 @4 E- l s[color=rgb(51, 102, 153) !important]复制代码8 G# l2 ?# k# K' D. P
堆处理
! U2 d& q, ^7 `, d3 s0 r, I* _- function [A] = MAX_HEAPIFY(A,i)
- l=2*i;%左节点序号
- r=2*i+1;%右节点序号
- %比较该节点与左右子节点的大小
- if l<=length(A) & A(l)>A(i)
- largest=l;
- else
- largest=i;
- end
- if r<=length(A) & A(r)>A(largest)
- largest=r;
- end
- %如果最大子节点变换,则交换,继续递归。
- if largest~=i
- temp=A(i);
- A(i)=A(largest);
- A(largest)=temp;
- A=MAX_HEAPIFY(A,largest);
- end
- end1 x. v0 \( E% a1 ?# |% \. Y
( d, D3 f# W. X0 ~4 T$ t ~) ~+ f4 _6 T- o2 _7 p+ i8 l$ z
! q$ O _. g) y
|
|