|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
0 P+ ^' O- G9 k' s1 a/ U
《算法导论(第三版)》第二章2.3，使用哨兵的归并排序。0 j7 d: [( M" z* p* P$ g2 n' X
主函数：
0 y/ K* U. L8 f5 m- l1 a; Q- A=[5 2 4 7 1 3 2 6];
- MERGE_SORT(A,1,length(A))2 d5 l% m o/ L- e% M: e
9 z. L. {: l7 x2 D( }4 U9 U" q0 \
( Y4 u% }/ E8 l# Q) q9 j7 F" ^0 ^: y递归：
7 K2 z% r" k! h2 }) p' E1 N y) P+ 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
+ r9 t. R8 D' S7 ?7 o; ^2 X
H8 O" a1 {( A. |3 K8 Y/ i) w
s+ U0 n6 G7 X# ^' `; H排序：
/ m& h( ]' p4 L- %%排序
- 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
- end; J1 X* b# h2 D1 S# T
+ X" ~' h6 Y9 D8 @) \
) E/ C+ P6 V5 R) z- r# q |
|
/1 
发表于 2020-2-3 09:50
收藏
淘帖
支持！
反对！