2.2.5.
B'
= N 1=, B2=,...,Bn=,
1. , >=2
B1,B2,...,Bm /2 ( (+1)/2)
, B(2i-1)-o B(2i)- ( 2i<=M ) m
.
N.
,
, .
:
9 / 7 / 18 / 3 / 52 / 4 / 6 / 8 / 5 / 13 / 42 / 30 / 35 / 26;
7,9 / 3,18 / 4 / 52 / 6 / 8 / 54 / 13 / 30 / 42 / 26 / 35;
3,7,9,18 / 4,6,8,52 / 5,13,30,42 / 26,35;
3,4,6,7,8,9,18,52 / 5,13,26,30,35,42;
3,4,5,6,7,8,9,13,18,26,30,35,42,52.
, , Q=N*log2(N),
N ,
log2(N) .
N, .
smerge s ,
merge.
/* */
double *smerge (double *s, int m, int n)
{ int l,low,up;
double *merge (double *, int, int, int);
l=1;
while(l<=(n-m))
{ low=m;
up=m-1;
while (l+up < n)
{ up=(low+2*l-1 < n) ? (low+2*l-1) : n ;
merge (s,low,up,l);
low=up-1;
}
l*=2;
}
return(a);
}
.
srecmg .
,
, ,
.29.
m (m+n)/2 n
+-----|---+------------+---|---+--------+---|-----+
s : | | | | | | | | |
+-----|---+------------+---|---+--------+---|-----+
|<---------1-------->|<------2------->|
.29. .
/* 1/2 */
double *srecmg (double *a, int m, int n)
{ double * merge (double *, int, int, int);
double * smerge (double *, int, int);
int i;
if (n>m)
{ i=(n+m)/2;
srecmg(a,m,i);
srecmg(a,i+1,n);
merge(a,m,n,(n-m)/2+1);
}
return (a);
}
|
|
