, , . , , . , . .
... , , . ("" - shell - . .) , , .
.2
"6 4 1 3 2 5". , . , . , , .
1 6 4 1 3 2 5
2 3 2 1 6 4 5
3 1 2 3 5 4 6
1 2 3 4 5 6
{ }
procedure Shell (var A: MyArray; n:integer);
const
t = 5;
var
i, j, k, s, m: integer;
h: array[1..t] of integer;
v: Integer;
begin
h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=2; h[5]:=1;
for m:= 1 to t do begin
k:=h[m];
s:=-k;
for i:= k+1 to n do begin
v:= A[i];
j:= i-k;
if s=0 then begin
s:= -k;
s:= s+1;
A[s]:= v;
end;
while (v<A[j]) and (j<n) do begin
A[j+k]:= A[j];
j:= j-k;
end;
A[j+k]:= v;
end;
end;
end; { }
, , . , . , , . -. , . , 9, 5, 3, 2, 1, . , , , ( , - ).
. "v<A[j]" . "j>0" "j<=n" , "A". . , , . , .. . . , , . n1.2. , .
|
|
|
... . . . , , . . "" . , "", , . , .
, "6 5 4 1 3 2" "4 " :
- : 6 5 4 1 3 2;
- : 4 3 1 4 5 6;
- : 1 2 3 4 5 6.
"2 3 1" "4 5 6". . , "" .
. , . , . . , , . . , .
{ }
procedure QuickSort(var A: MyArray; n:integer);
procedure qs(l, r: integer; var mas: MyArray);
var i, j: integer; v, y: Integer;
begin
i:=l; j:=r;
v:=mas[(l+r) div 2];
repeat
while mas[i]<v do i:= i+1;
while v<mas[j] do j:= j-1;
if y<=j then begin
y:= mas[i];
mas[i]:= mas[j];
mas[j]:= y;
i:= i+1; j:= j-1;
end;
until i>j;
if l<j then qs(l, j, mas);
if l<r then qs(i, r, mas)
end;
begin
qs(1, n, A);
end; { }
|
|
|
"qs". "A" "n" "qs". . , n log n,
n/6 log n. . n = ax v = log na. , , , 100 100*2, ..200 , log 100 2. 990 . , . , n. , . . , . , , , . , . .
, , , . , .
. , . , . , , .
. , :
function Search(A: MyArray; n:integer; key:Integer):integer;
var
t:integer;
begin
t:=1;
while (key<>A[t]) and (t<=n) t:=t+1;
if t>n then Search:=0
else Search:=t;
end; { }
, , . n/2 . , n . , . , , .
, , . . , . . , . , 4 1 2 3 4 5 6 7 8 9 , 5. 4, , .. 1 2 3 4 5. 3. 4 4 5. . log n. , .
|
|
|
function BSearch (A: MyArray; n:integer; key:Integer):integer;
var
low, high, mid: integer;
found:boolean;
begin
low:=1; high:=n;
found:=false; { }
while (low<=high) and (not found) do
begin
mid:=(low+high) div 2;
if key<A[mid] then high:=mid-1
else if key>A[mid] then low:=mid+1
else found:=true; { }
end;
if found then BSearch:=mid
else BSearch:=0; { }
end; { }
