EDA365电子论坛网
标题:
使用哨兵的归并排序。
[打印本页]
作者:
Zedd
时间:
2020-3-12 10:31
标题:
使用哨兵的归并排序。
《算法导论(第三版)》第二章2.3，使用哨兵的归并排序。
: E9 a$ b" \7 U6 s8 ^1 h# m/ H
主函数：
/ L6 i1 X7 S3 D% C4 C* E
A=[5 2 4 7 1 3 2 6];
MERGE_SORT(A,1,length(A))
# P) }) n6 j; {/ }
! r& y$ h0 f9 M$ s: p6 J
# f1 \, O- i3 Q. X% r
x9 W: u, H& R" Z. V* E' u3 t
, j/ s/ s# g0 e& u/ U
递归：
5 U/ m% X! G, A6 j0 A
%% 递归
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
) g+ g- |- P2 g4 t( E7 p
9 ~1 p/ |* n, L
/ ?3 h! h3 E* t! X1 h8 D
8 [4 K1 |9 |, a
1 v* a( N! x9 C9 t' e) ^
排序：
) N, W9 Y0 Z/ r$ j/ B
%%排序
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
( p' P5 r ^, W, T/ l2 {2 t3 c; o
/ Y2 O8 Q2 M7 ?; [8 @+ k1 e9 Y) |( P
作者:
helendcany
时间:
2020-3-12 18:17
使用哨兵的归并排序。
欢迎光临 EDA365电子论坛网 (https://bbs.eda365.com/)
Powered by Discuz! X3.2