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