|
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 |
|