神马品牌网低头娶媳妇 知乎:谁知道空间复杂度为o(1)的归并排序算法？
来源：百度文库 编辑：神马品牌网 时间：2024/05/01 00:54:42
我用的PASCAL
Const Maxn=100;
Var R,R1:Array[1..Maxn] of Integer;
n,i:Integer;
Procedure merge(s,m,t:Integer);
Var tmp:Array[1..Maxn] of integer;
i,j,k,p:Integer;
Begin
i:=s; j:=m+1; k:=s-1;
While (i<=m) and (j<=t) do
Begin
inc(k);
If R[i]<=R[j] Then Begin tmp[k]:=R[i]; inc(i) End
Else Begin tmp[k]:=R[j]; inc(j) End;
End;
If i<=m then For p:=i to m do Begin inc(k); tmp[k]:=R[p] End;
If j<=t then For p:=j to t do Begin inc(k); tmp[k]:=R[p] End;
For p:=s to t do R[p]:=tmp[p];
End;
Procedure m_sort(s,t:Integer);
Var m:Integer;
Begin
If s<t then
Begin
m:=(s+t) div 2;
m_sort(s,m);
m_sort(m+1,t);
merge(s,m,t);
End
End;
Begin
Readln(n);
For i:=1 to n do read(R[i]);
M_sort(1,n);
For i:=1 to n do write(R[i],' ');
End.