2.2.6.
, =< K1,K2,...,Kn>
B',< K1 >,B", ' - ,
1, " - , 1.
B',< K1 >,B" 1 ,
. B' "
.
, , Ki
< >.
:
9, 7, 18, 3, 52, 4, 6, 8, 5, 13, 42, 30, 35, 26
7, 3, 4, 6, 8, 5/ <9>/ 18, 52, 13, 42, 30, 35, 26
3, 4, 6, 5/<7>/ 8/ 9/ 13/ <18>/ 52, 42, 30, 35, 26
<3>/ 4, 6, 5/ 7/ 8/ 9/ 13/ 18/ 42, 30, 35, 26/ <52>
3/ <4>/ 6, 5/ 7/ 8/ 9/ 13/ 18/ 30, 35, 26/ <42>/ 52
3/ 4/ 5/ <6>/ 7/ 8/ 9/ 13/ 18/ 26/ <30>/ 35/ 42/ 52
. ,
B' " ,
N*log2(N) . ,
(N*N)/2 .
quick s
.
/* */
double * quick(double *s,int low,int hi)
{ double cnt,aux;
int i,j;
if (hi>low)
{ i=low;
j=hi;
cnt=s[i];
while(i < j)
{ if (s[i+1]<=cnt)
{ s[i]=s[i+1];
s[i+1]=cnt;
i++;
}
else
{ if (s[j]<=cnt)
{ aux=s[j];
s[j]=s[i+1];
s[i+1]=aux;
}
j--;
}
}
quick(s,low,i-1);
quick(s,i+1,hi);
}
return(s);
}
i j,
(. .30). i
cnt=s[low], , cnt, i
- , cnt. : s[i+1]<=cnt; s[i+1]>cnt
s[j]<=cnt; s[i+1]>cnt s[j]>cnt. i=j, cnt=s[i]
.
low i j hi
+---+-------+----+----+--------------+----+---------+---+
s:| | | + |+ +| | + | | |
+---+-------+--|-+|--|+--------------+--|-+---------+---+
+--+ +------------------+
1 2
.30. .
log2(N)
quick ( ).
,
N ,
N , N!,
C(N),
. , C(N)/N! <
2*N*ln(N).
. ,
- D(j,n) - j-
n>=0, .. D(j,n)=floor(n/m)%10, m=10^(j-1).
0,1,...,9 - (), .
,
, j=1,2,...,T.
P , i (i=1,N)
Bm, m=D(j,Ki), ,
j- m.
0,1,...,9 ,
.
=2 :
B=<09,07,18,03,52,04,06,08,05,13,42,30,35,26>.
-1:
B0=<30>, B1=< >, B2=<52,42>, B3=<03,13>, B4=<04>,
B5=<05,35>, B6=<06,26>,B7=<07>, B8=<18,08>, B9=<09>.
-1:
B=<30,52,42,03,13,04,05,35,06,26,07,18,08,09>
-2:
B0=<03,04,05,06,07,08,09>, B1=<13,18>, B2=<26>,
B3=<30,35>, B4=<42>, B5=<52>, B6=< >,B7=< >,B8=< >, B9=< >.
-2:
B=<03,04,05,06,07,08,09,13,18,26,30,35,42,52>.
, N T- ,
Q(N*T).
.
, 0,1,...,9
, ,
.
pocket
( q),
- ,
; a[i], b[i]
Bi.
/* e */
#include
#include
typedef struct str
{ long val;
struct str *n; } SP1;
main()
{ int i;
SP1 *q=malloc(sizeof(SP1)),*r;
SP1 *pocket(SP1 * ,int );
long a[14]={ 0,7,18,3,52,4,6,8,5,13,42,30,35,26 };
q->n=NULL;
q->val=a[0];
r=q;
printf(" %d",a[0]);
for(i=1;i<14;i++) /* */
{ r->n=malloc(sizeof(SP1));
r->val=a[i];
(r->n)->n=NULL;
r=r->n;
printf(" %d",a[i]);
}
r=pocket(q,2);
printf("\n"); /* */
while (r!=NULL)
{ printf(" %d",r->val);
r=r->n;
}
}
/* */
SP1 *pocket(SP1 *q,int t)
{ int i,j,k,m=1;
SP1 *r, *gg, *a[10], *b[10];
gg=q;
for(j=1;j<=t;j++)
{ for(i=0;i<=9;i++) a[i]=(b[i]=NULL);
while(q!=NULL)
{ k=((int)(q->val/m))%(int)10;
r=b[k];
if (a[k]==NULL) a[k]=q;
else r->n=q;
r=b[k]=q;
q=q->n;
r->n=NULL;
}
for(i=0;i<=9;i++)
if (a[i]!=NULL) break;
q=a[i];
r=b[i];
for(k=i+1;k<=9;k++)
if(a[k]!=NULL)
{ r->n=a[k];
r=b[k];
}
m=m*10;
}
return (gg);
}
.31
- .
+------ a[k]- - - >++<--X- q ---+
| +--+--+ +--+--+++->+--+--+ +>+--+--+ +--+--+
+>| | -| ->| | +|--->| | +|X-+ | | | - ->| | -|->+
+--+--+ +>+--+-|+ +>+--+-|+ +>+--+--+ +--+--+ =-=
X X | X
| =-= | =-=
+- p,b[k] -+
.30. .
.
, D(j,n) j-
n.
0 1;
, 0 1
. 0
1.
j- ,
.
.
B=
m=(MIN+MAX)/2.
1 2, 1 , m,
2 - , m. 1 2
.
|
|
