|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
《算法导论(第三版)》第六章，堆排序
0 t5 O8 E1 G0 b8 I
) v4 r: B& M( _/ m* ]! W% ^( G( E# Dmatlab使用堆比较麻烦，且不好理解，就直接使用堆排序的思想，直接操作数组进行示意，简化代码。( T& }8 P8 p* d$ p9 P
1 T s/ G' O5 @5 q' HHEAPSORT! O1 t* G0 z9 j6 ] T, R$ W3 W0 @9 h
- 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%结果
8 Z+ z C2 a; K# J& F# ~
, G; d4 \# s- W1 w+ p- t a
/ G! r+ G2 U/ B
8 Z5 s( t# Z. V& x建立堆+ ?% U7 c: ?' z3 T
- function [A] = BUILD_MAX_HEAP(A)
- for i=floor(length(A)/2):-1:1
- A=MAX_HEAPIFY(A,i);
- end
- end' Y$ L, e4 n' ]3 t: G+ w
: l. N+ m6 V: T/ y0 @8 M[color=rgb(51, 102, 153) !important]复制代码 W% `! F+ P) A; `7 Y X6 B
堆处理- O: A; D# H! a3 K3 k
- 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
- end
3 \$ R5 ]* z U# N5 d' ~% x! B
8 Y2 P" q& S H4 s' [$ d
q1 P. p9 q9 L( d' R" U- K
! D, \+ i; s* ~. L) Y+ U Y$ n |
|
/1 
发表于 2020-3-11 11:18
收藏
淘帖
支持！
反对！