|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
《算法导论(第三版)》第二章2.3，使用哨兵的归并排序。3 \; M3 n W. R) B
主函数：
+ X2 D$ h9 h- g) X& G- A=[5 2 4 7 1 3 2 6];
- MERGE_SORT(A,1,length(A))9 p' |, X, n% ^6 @) Y, N2 o' }- L
2 c F" [6 s# ]8 I2 j, t
, k# m8 g, m/ ~6 J7 o
9 h% X6 H+ u6 O* f! ]. _' w9 }! I. p2 A5 z7 g" h
递归：
( k) s6 q3 @6 Y5 C. d8 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 V3 s$ z- f7 x+ |& t+ }" b1 |! S2 o
. E0 L* F9 f9 v: g# A* v3 N3 G6 t
& m7 c: M8 D' [
' Q8 y, l K: h" }# n) ]9 n, g8 |$ ^& |7 h) A+ m1 _; @* v {
排序：5 v- d) A5 z# R* D
- %%排序
- 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
- end4 M1 X. p8 ?: X
9 G) a% v, n) m/ f% j" z' Z0 `& I |
|
/1 
发表于 2020-3-12 10:31
收藏
淘帖
支持！
反对！