1
:
- ;
- .
: , , .
- , >, <, ³, £. , . , .
, - . , - , .
. , . , . .
, ( ; ; ) . , , .
, , , ( , , , .), , ( , , ) .
, .
, . .
.
, , . :
for i:= 1 to N dobegin <__k+1__A[i] ___B> B[k+1]:= A[i];end;B[k+1] B[k+1]. k A[i] , , , A[i]. , , A[i]. k :
|
|
, T(n2) ( , n ) O(n) ( ).
2 : . .
A[1], A[2],..., A[i-1], A[i],...,A[n] . A[i] , . , A[i], ( ) , A[i]. A[i], ( - ) . A[i] .
, i=2.
:
for i:= 2 to n dobegin Tmp:= A[i]; j:= i-1; while (A[j]>Tmp)and(j>1) do begin A[j+1]:= A[j]; Dec(j) end; A[j+1]:= Tmp;end;T(n2), , Tmin(n). , , , . , .
, , . , A[i] . , . ( A[i], , , , ). .
A[i] , , A[i-h], A[i-2h], A[i-3h] , h - . , h- , h, .
, : h, . , h=1.
hi, hi-1, hi-2,..., h1, . , hi+1=3hi+1, h1=1. hm-2, m - , hm³ n. hm-2 , hm-2³ [n/9].
|
|
:
Step:= 1;while Step < N div 9 do Step:= Step*3 + 1;Repeat for k:= 1 to Step do begin i:= Step + k; while i <= N do begin x:= A^[i]; j:= i - Step; while (j >= 1) and (A^[j]>x) do begin A^[j + Step]:= A^[j]; Dec(j); end; A^[j + Step]:= x; Inc(i, Step); end; end; Step:= Step div 3;until Step=0;, , 1,66n1,25 .
A[i+1], A[i+1],..., A[n] A[1], A[2],..., A[i]. . , , .
, . A[i] .
for i:= N downto 2 dobegin MaxIndex:= 1; for j:= 2 to i do if A[j]>A[MaxIndex] then MaxIndex:= j; Tmp:= A[i]; A[i]:= A[MaxIndex]; A[MaxIndex]:= Tmp;end;T(n2) ( , n ).
. , A[1]. , , .
, . , ( ), -. , -.
1, 2,...: k 2*k 2*k+1, - . , (0 - , 1 - ). , 910=10012. 1 ( 1). 0, ( 210=102), 0 - ( 410=1002), 1 - 910=10012. .
, .
A[1]..A[n] - , . 1 n; A[i] , i. . k. , A[1]..A[n] : A[1]..A[k] , A[k+1].. A[n] - , .
, .
. 1 k. s 2*s 2*s+1. k, ; . 2*s=k, s (2*s).
|
|
s 1..k "" s: s (, .. - , 1..k).
s , - s-; s- , . ( , .)
:
k:= n... 1- ;while k<>1 dobegin... A[1] A[k]; k:= k - 1; {A[1]..A[k-1] <= A[k] <=...<= A[n]; 1- , , , }... 1- end;s- . :
{s- , , , }t:= s;{s- , , , t}while ((2*t+1<=k) and (A[2*t+1]>A[t])) or ((2*t<=k) and (A[2*t]>A[t])) dobegin if (2*t+1<=k) and (A[2*t+1]>=A[2*t]) then begin... A[t] A[2*t+1]; t:= 2*t + 1; end else begin... A[t] A[2*t]; t:= 2*t; end;end;, . s- , t, . t. , . , t- t , . ( t , .) :
while t, dobegin if then begin... t ; t:= end else begin { - }... t ; t:= endendt ( t-). , . s- , ( ), .
, 1- :
k:= n;u:= n;{ s- s>u }while u<>0 dobegin {u- , }... u- ; u:=u-1;end;:
procedure Sort;Var u, k: Integer;procedure Exchange(i, j: Integer);Var Tmp: Integer;begin Tmp:= x[i]; A[i]:= A[j]; A[j]:= Tmp;end;procedure Restore(s: Integer);Var t: Integer;begin t:=s; while ((2*t+1<=k) and (A[2*t+1]>A[t])) or ((2*t<=k) and (A[2*t]>A[t])) do begin if (2*t+1<=k) and (A[2*t+1]>=A[2*t]) then begin Exchange(t, 2*t+1); t:= 2*t+1; end else begin Exchange(t, 2*t); t:= 2*t; end; end;end;begin k:=n; u:=n; while u<>0 do begin Restore(u); Dec(u); end; while k<>1 do begin Exchange(1, k); Dec(k); Restore(1); end;end;, , Tmax(n*log(n)) ( n Restore, log(n) ), n.
|
|
.
- . : . , : ( ), . .
, .
, , , , . Flag - :
for i:= N-1 downto 1 dobegin Flag:= false; for j:= 1 to i do if a[j]>a[j+1] then begin Tmp:= A[j]; A[j]:= A[j+1]; A[j+1]:= Tmp; Flag:= true; end; if not Flag then Break;end;T(n2) ( , n ) (i, j, Tmp, Flag). Flag T(n).
()
, , .
. , .
, , : , , , - . , ( ). , , .
, :
procedure Sort;procedure QuickSort(a, b: Longint);Var x: Longint; { }begin x:= __;... : 1) A[a]..A[i]; 2) A[i+1]..A[j-1]; 3) A[j]..A[b] if i>a then QuickSort(a, i); if b>j then QuickSort(j, b);end;begin Sort(1, N);end;- , , , . , , ( , ), : ( , ) :
i:= A[l]; y:= A[(l+r)div 2]; j:= A[r];if i<=y then if y<=j then x:= (l+r)div 2 else if i<=j then x:= r else x:= lelse if y>=j then x:= (l+r)div 2 else if i>=j then x:= r else x:= l;A[x] , , A[x], A[x], , A[x]. , A[i], A[x], , , - A[j], A[x]. i j, , , A[i] A[j], A[i] A[j].
i:= l; j:= r; x:= A[x];repeat while A[i] < x do Inc(I); while x < A[j] do Dec(j); if i <= j then begin y:= A[i]; A[i]:= A[j]; A[j]:= y; Inc(i); Dec(j); end;until i > j;. , - , , , , . , QuickSort , ( ) N . N O(N). , QuickSort . O(log(N)).
|
|
:
procedure Sort;procedure QuickSort(a, b: Longint);Var x: Longint; { }begin i:= A[l]; y:= A[(l+r)div 2]; j:= A[r]; if i<=y then if y<=j then x:= (l+r)div 2 else if i<=j then x:= r else x:= l else if y>=j then x:= (l+r)div 2 else if i>=j then x:= r else x:= l; i:= l; j:= r; x:= A[x]; repeat while A[i] < x do Inc(i); while x < A[j] do Dec(j); if i <= j then begin y:= A[i]; A[i]:= A[j]; A[j]:= y; Inc(i); Dec(j); end; until i > j; if l-j<i-r then begin if l < j then QuickSort(l, j); if i < r then QuickSort(i, r); end else begin if i < r then Sort(i, r); if l < j then Sort(l, j); end; end;begin QuickSort(1, N);end;Tmax(N2) ( , ), . T(N*log(N)).
, .
k - . A[1]..A[n] k. ( - A[1]..A[k], A[k+1]..A[2k] ..) , n k. k-, k .
, 1-, 1 . k- n<=k, .
:
k:=1;while k < n dobegin... k- 2k-; k:= 2 * k;end;k- 2k-. k . . , 2k- :
t:=0;while t + k < n dobegin p:= t; q:= t+k;...r:= min(t+2*k, n); { min }... A[p..q-1] A[q..r] t:= r;end;- B. p0 q0 , , s0 - B . :
B[s0+1]:=A[p0+1];
Inc(p0);Inc(s0); B[s0+1]:=A[q0+1];Inc(q0);Inc(s0);( ) :
(1) (p0 < q);
(2) (q0 = r) , [(q0 < r) (A[p0+1] <= A[q0+1])].
. ,
p0:= p; q0:= q; s0:= p;while (p0<>q)or(q0<>r) dobegin if (p0<q)and((q0=r)or((q0 < r) and (A[p0+1]<=A[q0+1]))) then begin B[s0+1]:= A[p0+1]; Inc(p0); Inc(s0); end else begin B[s0+1]:= A[q0+1]; Inc(q0); Inc(s0); end;end;( , ; .)
:
k:= 1;while k < N dobegin t:= 0; while t+k < N do begin p:= t; q:= t+k; if t+2*k>N then r:= N else r:= t+2*k; p0:= p; q0:= q; s0:= p; while (p0<>q) or (q0<>r) do begin if (p0<q) and ((q0=r)or((q0<r)and (A[p0+1]<=A[q0+1]))) then begin B[s0+1]:= A[p0+1]; Inc(p0); end else begin B[s0+1]:= A[q0+1]; Inc(q0); end; Inc(s0); end; t:= r; end; k:= k shl 1; A:= B;end;N ( ). , N*log(N) ( k- 2k- N k log(N) ).
, , .
, .
M (, 1 M) . Amount, . i A, i, Amount[i]:
for i:= 0 to M do Amount[i]:= 0;for i:= 1 to N do Inc(Amount[A[i]]);Amount[1] A 1, Amount[2] A 2 .. , A (, Amount):
p:= 1;for i:= 0 to M do for j:= 1 to Amount[i] do begin A[p]:= i; Inc(p); end;, N . , . T(M+N) (M , Amount, M ). O(M), M.
, M, - M. , M>>N, , .
M+N, 0 S, S>>M.
M- K .
M N ( , O(M+N)).
:
for i:= K downto 1 dobegin for j:= 1 to N do begin L:=<i- A[j] M- >;... A[j] L- ; end;... A for j:= 1 to M do... j- Aend;, , i- . . , , .
i , i , i , .
i=1, .
, S=M, : j , j. , , j, j 1 S. A . .
, T(K*N), , K , (, ) . M+N. , N.
, , . , , . 60 , , , . 500, 1000, 3000, 5000, 8000, 10000, 30000, 60000. . , : , .
, .
) , :
0.08 | 0.31 | 2.76 | 7.67 | 19.67 | ||||
0.03 | 0.06 | 0.60 | 1.66 | 4.22 | 6.58 | 59.62 | ||
0.02 | 0.05 | 0.43 | 1.12 | 2.72 | 4.24 | 35.62 | ||
0.03 | 0.02 | 0.06 | 0.09 | 0.11 | 0.13 | 0.38 | 0.77 | |
0.01 | 0.10 | 0.92 | 2.54 | 6.51 | 10.17 | |||
0.02 | 0.02 | 0.11 | 0.20 | 0.33 | 0.42 | 1.39 | 3.02 | |
0.07 | 0.27 | 2.43 | 6.75 | 17.28 | ||||
0.00 | 0.00 | 0.01 | 0.03 | 0.03 | 0.04 | 0.13 | 0.27 | |
0.00 | 0.00 | 0.02 | 0.03 | 0.05 | 0.06 | 0.20 | 0.38 | |
0.00 | 0.00 | 0.00 | 0.00 | 0.01 | 0.01 | 0.01 | 0.02 |
) :
0.08 | 0.32 | 2.65 | 7.26 | 18.46 | ||||
0.00 | 0.00 | 0.00 | 0.00 | 0.01 | 0.01 | 0.01 | 0.03 | |
0.00 | 0.00 | 0.01 | 0.02 | 0.02 | 0.05 | 0.15 | 0.29 | |
0.02 | 0.02 | 0.04 | 0.08 | 0.09 | 0.12 | 0.31 | 0.63 | |
0.02 | 0.11 | 0.92 | 2.54 | 6.53 | 10.20 | |||
0.01 | 0.03 | 0.11 | 0.19 | 0.34 | 0.43 | 1.45 | 3.11 | |
0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.01 | 0.01 | 0.02 | |
0.00 | 0.00 | 0.01 | 0.02 | 0.03 | 0.04 | 0.11 | 0.22 | |
0.00 | 0.01 | 0.02 | 0.03 | 0.04 | 0.05 | 0.18 | 0.36 | |
0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.01 | 0.01 | 0.02 |
) :
0.09 | 0.32 | 2.64 | 7.26 | 18.47 | ||||
0.02 | 0.13 | 1.16 | 3.26 | 8.37 | 13.08 | |||
0.01 | 0.00 | 0.03 | 0.16 | 0.21 | 0.27 | 2.09 | 8.02 | |
0.02 | 0.03 | 0.06 | 0.06 | 0.10 | 0.11 | 0.32 | 0.64 | |
0.02 | 0.11 | 0.91 | 2.54 | 6.51 | 10.19 | |||
0.00 | 0.02 | 0.10 | 0.18 | 0.30 | 0.39 | 1.32 | 2.85 | |
0.06 | 0.29 | 2.95 | 8.35 | 21.60 | ||||
0.00 | 0.00 | 0.01 | 0.01 | 0.03 | 0.04 | 0.11 | 0.24 | |
0.01 | 0.01 | 0.03 | 0.03 | 0.05 | 0.07 | 0.19 | 0.37 | |
0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.01 | 0.03 |
. , . , , , . AMD-K5-PR133/32Mb EDO/850Mb MS-DOS 7.0, WINDOWS 95. .
:
Tmax | Tmid | Tmin | Omax | |
n2 | n | |||
n2 | n | |||
n2 | n1,25 | n | ||
n2 | ||||
n*log(n) | ||||
n2 | n | |||
n2 | n*log(n) | log(n) | ||
n*log(n) | n | |||
n | n |
.
- , , , <~3000 . , , , , .
- , , , , .
- , : , , .
- .
- ( , T(N2), ), , . , , , N.
- , n, .
- ? ?
- ? ? ?
- , ?
- T(1)?
- ( )?
- , .
- ( )?
- , .
- ? ?
- , .
- , T(n*log(n))? (: )
- O(log(n)) ?
- , .
- , .
.
, , .
:
- ;
- , ;
- , ;
- ;
- .
- .
- .
- .
- .
- .
- .
: , ; , - . , .
, .
1. . n*log n.
. , , .
2. k- . n*log n.
. , , k.
3. n [A[i], B[i]] (i=1..n), A[i] , B[i] .
k, , k (" "). - n*log n.
. ( , ). , . 1, - . , : ( ), - ( ).
4. n . (n-1)- , . ( .) n*log n.
. x-, x- - y-. .
5. , .
. (.. x-) . , .
6. n . - , . ( , , .) n*log n.
. - , . , , . ( , , )
7. , 0, 1 2. 0 , 2 . n.
. .
8. . , . n*log n.
. , . ( T(n2)) , , , .
9. A, aij , i- j- . ( ; ).
10. .
. .
11. . n. 1 1000000000.
. .