EDA365电子论坛网
标题:
MATLAB之归并排序
[打印本页]
作者:
haidaowang
时间:
2020-2-3 09:50
标题:
MATLAB之归并排序
( B! p r+ F- x' j
《算法导论(第三版)》第二章2.3，使用哨兵的归并排序。
' e: {; i; L5 s* p" y
主函数：
0 H+ B% K9 G) B+ A. }
A=[5 2 4 7 1 3 2 6];
MERGE_SORT(A,1,length(A))
- f- s- o% {6 H% K! e! G- C! e
4 \( C+ m h/ U& A9 V
5 V* l0 a. N8 l) I4 k, ]& ?' W t
递归：
$ [. B ~' M; |' ~0 A+ H8 T
%% 递归
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
; M2 ]* `# _" |( R" A6 {: ]; L4 q
7 }& w1 V. C" j$ i( T" [
: I2 Z! d6 H: n( U* [
排序：
+ n1 R" _+ k2 ]
%%排序
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
- `$ [) ]6 v1 d- n+ _
3 R; Z* E r9 U7 R" x
" s( Y# K$ `$ {: A# g% B
作者:
ExxNEN
时间:
2020-2-3 19:07
MATLAB之归并排序
欢迎光临 EDA365电子论坛网 (https://bbs.eda365.com/)
Powered by Discuz! X3.2