使用哨兵的归并排序。

Zedd

《算法导论(第三版)》第二章2.3，使用哨兵的归并排序。
% Q0 g/ q- P  q  G主函数：
* O! M5 [! g5 \, e( w5 R

• A=[5 2 4 7 1 3 2 6];
• MERGE_SORT(A,1,length(A))
  

# H, k* M- c, S* [

递归：
+ A+ s/ s" Y- w

• %% 递归
• 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
  ! X; ~: Q% e; B  R! T' @. _: P( \; F

4 Y2 Q/ G2 g* R5 a1 @' q2 D
8 I# v0 ]' I0 Q9 o$ E# V2 L
+ E; d# w4 L/ ^+ S% B+ y5 e
. N' R) |% p( R6 E& v1 g/ s, Y排序：
5 H! S8 C# f* N* T# ?( v- w+ V2 q8 A3 s

• %%排序
• 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
  # E( _3 e4 c8 d+ w( \* y

3 d) @& @, A3 a

helendcany

使用哨兵的归并排序。