|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
4 W2 d+ f S+ T, G0 ]1 O! B3 L
《算法导论(第三版)》第二章2.3，使用哨兵的归并排序。0 b/ N1 }, z/ c0 Y( D/ K
主函数：4 x/ r8 w% @- i. F) I
- A=[5 2 4 7 1 3 2 6];
- MERGE_SORT(A,1,length(A))
+ ^6 D8 \/ t7 v8 O) o
& U+ s9 e" }/ l$ Z! ^, r1 @0 W/ x' s7 o' t2 C
递归：& h2 d8 t; b, Q
- %% 递归
- 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# R# ^ b/ U) P
" c7 J8 o# @2 S
( K7 c, S! l B% }5 a- P排序：3 P8 f( Z! M/ z! j, w
- %%排序
- 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. f5 E- i0 K3 E7 G0 Y' G
& O7 e j. n, J T
+ p* @( J6 A8 z. b4 Z7 f! Y$ v" [& i
|
|
/1 
发表于 2020-2-3 09:50
收藏
淘帖
支持！
反对！