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

使用哨兵的归并排序。

[复制链接]

该用户从未签到

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

EDA365欢迎您登录!

您需要 登录 才可以下载或查看,没有帐号?注册

x
《算法导论(第三版)》第二章2.3,使用哨兵的归并排序。( ^& c- }5 w7 f. s' n( \% a
主函数:
) j: E" r: M$ v$ I
  • A=[5 2 4 7 1 3 2 6];
  • MERGE_SORT(A,1,length(A))
    7 s  Y. e+ Y+ G" \1 ?6 p1 M
: y4 _$ ]8 v; R( i& U9 m" M1 ]

: r3 p5 ^& G' G4 B; r! ^! W7 j- L0 o

+ @2 R' |2 q( _& r递归:' Y/ w7 y& @1 y7 s* E$ ~$ u
  • %% 递归
  • function [A] = MERGE_SORT(A,p,r)%A是数组,p在前,q在后
  •     if p<r %判断是否到底,相等即只有一位数,不再分解
  •      q=floor((p+r)/2);%中间值,首尾相加除以2,再向下取整;
  •      A=MERGE_SORT(A,p,q);%前半段
  •             A=MERGE_SORT(A,q+1,r);%后半段
  •             A=MERGE(A,p,q,r);%排序
  •     end
  • end3 h% c4 [& W: s8 I% B; H  t
6 D/ G( O; b& F/ x1 h

; J1 d( [- @* l& f0 J! E9 B- W, u( l; e2 i' t" j  N
* g( u0 i$ h3 p% X" x
排序:
5 ^+ T, r6 ]# ]0 p6 ^. E' K
  • %%排序
  • function [A] = MERGE(A,p,q,r)%A是数组,p<=q<=r
  • L=A(p:q);%前半段
  • R=A(q+1:r);%后半段
  • L(end+1)=inf;%前半段哨兵   哨兵的用处:避免某个半段值已用完,无法做比较。
  • R(end+1)=inf;%后半段哨兵
  • i=1;%序号
  • j=1;%序号
  • for k=p:r %进行排序
  •         if L(i)<=R(j) %判断前后两个半段是谁先放
  •                 A(k)=L(i);
  •                 i=i+1;
  •         else
  •                 A(k)=R(j);
  •                 j=j+1;
  •         end
  • end
  • end6 V/ Z! |$ T; O% h# Y

& L# S4 F9 y) n. F+ L9 l

该用户从未签到

2#
发表于 2020-3-12 18:17 | 只看该作者
使用哨兵的归并排序。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

关闭

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

EDA365公众号

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

GMT+8, 2025-6-15 18:40 , Processed in 0.078125 second(s), 23 queries , Gzip On.

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

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

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