找回密码
 注册
关于网站域名变更的通知
查看: 336|回复: 1
打印 上一主题 下一主题

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

[复制链接]

该用户从未签到

跳转到指定楼层
1#
发表于 2020-3-11 11:18 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式

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
您需要登录后才可以回帖 登录 | 注册

本版积分规则

关闭

推荐内容上一条 /1 下一条

EDA365公众号

关于我们|手机版|EDA365电子论坛网 ( 粤ICP备18020198号-1 )

GMT+8, 2025-8-23 15:08 , Processed in 0.109375 second(s), 23 queries , Gzip On.

深圳市墨知创新科技有限公司

地址:深圳市南山区科技生态园2栋A座805 电话:19926409050

快速回复 返回顶部 返回列表