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

使用哨兵的归并排序。

[复制链接]

该用户从未签到

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

EDA365欢迎您登录!

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

x
《算法导论(第三版)》第二章2.3,使用哨兵的归并排序。) Z' q" W$ n3 \  ]; I7 E) r
主函数:
: S1 _! @1 Q6 H
  • A=[5 2 4 7 1 3 2 6];
  • MERGE_SORT(A,1,length(A))
    ' ^2 g2 {% x( y- h- O$ M
: Q3 ?: t! d9 n: b+ S
& w) y6 D0 h$ x* g( G  P
  y1 ]6 |+ q% `+ Q" X7 a& X* D* N

$ m  Y) h* t/ I" |. p' @# h递归:
, H( x$ {" E5 [: M8 T) [9 b
  • %% 递归
  • 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
  • end" J3 I! x+ B2 J& I
& m: j7 S( w: K, d1 e! A

; ~% H9 d  @& Z9 ]+ I' a- m' T0 F8 I8 O" R7 k) A
' ?2 a5 Q5 P9 h
排序:2 I. r) K+ N' N6 t3 {
  • %%排序
  • 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
  • end9 z* ^! C, N" u' T

, i1 {. ^; }% m& T4 |" ^4 x# G

该用户从未签到

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

本版积分规则

关闭

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

EDA365公众号

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

GMT+8, 2025-6-17 20:44 , Processed in 0.062500 second(s), 23 queries , Gzip On.

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

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

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