《算法导论(第三版)》第六章，堆排序

Zedd

《算法导论(第三版)》第六章，堆排序

1 A0 X0 c- [. J6 Q4 p5 c7 zmatlab使用堆比较麻烦，且不好理解，就直接使用堆排序的思想，直接操作数组进行示意，简化代码。
6 z2 |% k7 `( z9 Q3 j7 F6 j) S
0 H7 ^2 w& q) W' t9 V0 N3 [/ `HEAPSORT

• 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%结果
  

: k' c0 v3 }0 H' a( y' d. K& i
" p+ G$ P1 N, P5 f$ I0 E
建立堆
) K% G2 e" [# v- w3 v2 ^$ w

• function [A] = BUILD_MAX_HEAP(A)
• for i=floor(length(A)/2):-1:1
•     A=MAX_HEAPIFY(A,i);
• end
• end
  

[color=rgb(51, 102, 153) !important]复制代码
$ {- Z1 y' Z8 {( I; e' R堆处理

• 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
  1 R" ?: ?, J8 D6 R! b  o; S+ i

8 Z* @6 x8 y8 H: t
( K- U4 D; @6 i1 t" z& J! D

wu68aq

堆排序。