.................................................................................................................................................................................... 5
.................................................................................................................................................................................. 5
............................................................................................................................................................. 6
............................................................................................................................................... 6
......................................................................................................................................................................................... 7
.............................................................................................................................................................................. 7
................................................................................................................................................. 7
...................................................................................................................................................................................... 7
............................................................................................................................................................................. 8
.................................................................................................................................................................. 9
.................................................................................................................................................. 9
....................................................................................................................................................... 10
........................................................................................................................................................ 13
........................................................................................................................................ 15
......................................................................................................................................................... 16
.................................................................................................................................................................................... 16
........................................................................................................................................................................... 17
|
|
..................................................................................................................................................... 18
.................................................................................................................................................................................... 18
........................................................................................................................................................................... 19
....................................................................................................................................................... 22
................................................................................................................................................................ 23
................................................................................................................................................ 23
....................................................................................................................................................... 24
........................................................................................................................................................ 27
.................................................................................................................................................................................... 29
-...................................................................................................................................................................... 29
.................................................................................................................................................................................... 30
........................................................................................................................................................................... 32
.................................................................................................................................. 34
.................................................................................................................................................................................... 34
........................................................................................................................................................... 35
........................................................................................................................................................................... 36
- ............................................................................................................................................. 38
.................................................................................................................................................................................... 38
................................................................................................................................................................................. 39
|
|
........................................................................................................................................................................... 40
................................................................................................................................................................ 45
............................................................................................................................................................... 45
.................................................................................................................................................................................... 45
........................................................................................................................................................................... 46
....................................................................................................................................................... 49
................................................................................................................................................... 50
.................................................................................................................................................................................... 51
........................................................................................................................................................................... 53
-................................................................................................................................................................................. 53
.................................................................................................................................................................................... 53
........................................................................................................................................................................... 55
............................................................................................................................................ 55
...................................................................................................................................................... 55
.................................................................................................................................................... 56
...................................................................................................................................................... 56
a-b-....................................................................................................................................................... 60
...................................................................................................................................... 66
.......................................................................................... 68
................................................................................................................................................................. 69
............................................................................................................................................................................ 74
.............................................................................................................................................................................. 74
|
|
</DIV>
, , , . , () . , , , , . , , .
.1.1 . , . 1.2. 7; , A [6].
. 1.1.
int function SequentialSearch (Array A, int Lb, int Ub, int Key); begin for i = Lb to Ub do if A (i) = Key then return i; return -1; end; |
. 1.2.
, , (. 1.3). Lb Ub , , , . . , , . , Ub (M 1) . , . , , , . , 6, , .
- . , , 1023, 511 , - 255. , 1023 10 .
. , . , 18 . 1.1, A [3]: A [6] - 18 A [3]. . / .
int function BinarySearch (Array A, int Lb, int Ub, int Key); begin do forever M = (Lb + Ub)/2; if (Key < A [ M ]) then Ub = M - 1; else if (Key > A [ M ]) then Lb = M + 1; else return M; if (Lb > Ub) then return -1; end; |
. 1.3.
. 1.4 , , ; "" . , X P , 18 :
X->Next = P->Next;
P->Next = X;
. , , , , .. P. , . , / , . , .
|
|
. 1.4.
. - . - . , , O (n) ( : n). , n , . O (), , , . , , O (n 2), , , , . , , 1.1, , . O (lg n) . 2 1, n . - . , lg n.
1.1.
n | lg n | n lg n | n 1.25 | n 2 |
2,048 | 1,024 | 65,536 | ||
4,096 | 49,152 | 32,768 | 16,777,216 | |
65,536 | 1,048,565 | 1,048,476 | 4,294,967,296 | |
1,048,476 | 20,969,520 | 33,554,432 | 1,099,301,922,576 | |
16,775,616 | 402,614,784 | 1,073,613,825 | 281,421,292,179,456 |
, 1.1 , 1048476 O (lg n) 20 , O (n 1.25) - 33 , O (n 2) - 12 . O -. .
...
, , . , , - ! . , , , , .
, . , , .
<DIV ALIGN=right></DIV>
, - , ( , , QuickSort). - , , , . - , . -, - QuickSort, .
- . . , , , . , . , - O(n2). [1998] [Knuth].
.2.1(a) 3. , , - , , 3. .2.1(b) 1. , .2.1(c) , 2 .
. 2-1.
n, n -1 . n -1 , O (n 2).
|
|
. , , , , . , - , .
. typedef T compGT , , .
//
typedef int T; /* , */
typedef int tblIndex; /* */
#define compGT(a,b) (a > b)
void insertSort(T *a, tblIndex lb, tblIndex ub) {
T t;
tblIndex i, j;
/**********************************
* a[lb..ub] *
**********************************/
for (i = lb + 1; i <= ub; i++) {
t = a[i];
/* */
/* . */
for (j = i-1; j >= lb && compGT(a[j], t); j--)
a[j+1] = a[j];
/* */
a[j+1] = t;
}
}
. Pascal. .
. , in situ ( ) , A B, . , , , .. . . n .
(n*log(n)), , , n^2 . :
1. .
2. , , . , .
3. , , n , n.
, in situ, :
1. .
2. .
3. .
. A, in situ, item index, :
type index = 0.. n;
var A: array [1.. n] of item;
( , ) , . .
. () A[1],...,A[i-1] A[i],...,A[n]. , i=2 i , , .
.
44 55 12 42 94 18 06 67
i=2 44 55 12 42 94 18 06 67
i=3 12 44 55 42 94 18 06 67
i=4 12 42 44 55 94 18 06 67
i=5 12 42 44 55 94 18 06 67
i=6 12 18 42 44 55 94 06 67
i=7 06 12 18 42 44 55 94 67
i=8 06 12 18 42 44 55 67 94
. :
for i:= 2 to n do
begin x:= A[i]
" A[1]...A[i]"
end
, .. "" , A[j] , A[j] . , "" :
A[j] , .
.
(""). , A[0] = . (, A 0,...,n). .
procedure StraightInsertion;
var i,j: index; x: item;
begin
for i:= 2 to n do
begin x:= A[i]; A[0]:= x; j:= i-1
while (x.key < A[j].key) do
begin A[j+1]:=A[j]; j:=j-1;
end;
A[j+1]:=x;
end;
end;
, , A[1],...,A[i], , . , . , .
procedure BinaryInsertion;
var i,j,l,r,m: index; x: item;
begin
for i:= 2 to n do
begin x:=A[i]; l:=1; r:=i-1;
while (l<=r) do
begin m:=(l+r) div 2;
if (x.key<A[m].key) then r:=m-1 else l:=m+1;
end;
for j:=i-1 downto l do A[j+1]:=a[j];
A[l]:=x;
end;
end;
. . , . . . , . , .. , . .
. , , . . (, ), , , .
, , , , . , , . . , - ... , . , .
:
1. .
2. A.
n-1 , n-2 , - . :
44 55 12 42 94 18 06 67
i=2 06 55 12 42 94 18 44 67
i=3 06 12 55 42 94 18 44 67
i=4 06 12 18 42 94 55 44 67 (42 )
i=5 06 12 18 42 94 55 44 67
i=6 06 12 18 42 44 55 94 67 (55 )
i=7 06 12 18 42 44 55 94 67
i=8 06 12 18 42 44 55 67 94
:
for i:= 1 to n-1 do
begin " k A[i]...A[n]
" A[i] A[k]"
end
, , . . , . .
procedure StraightSelection;
var i,j,k: index; x: item;
begin for i:= 1 to n-1 do
begin k:= i; x:= A[i];
for j:= i+1 to n do
if (A[j].key < x.key) then
begin k:= j; x:= A[j];
end;
A[k]:= A[i]; A[i]:= x;
end;
end;
. , , , . , . .
, , ( ) . , . . . . , , . , , . , , , . . . 1. . . . N-1 . . , .
procedure ViborSPodschetom;
var
i,j:index;
count: array [index] of integer;
B: array [index] of item;
begin
for i:=1 to n do count[i]:=0;
for i:=1 to n-1 do
begin
for j:=i+1 to n do
begin
if (A[i].key<A[j].key) then count[j]:=count[j]+1 else count[i]:=count[i]+1;
end;
end;
for i:=1 to n do B[count[i]+1]:=A[i];
for i:=1 to n do A[i]:=B[i];
end;
( - ) . . , (N-1) (N). , . .
. , , . , . , , , . , , . 0. .
,
. i=2 3 4 5 6 7 8
44 06 06 06 06 06 06 06
55 44 12 12 12 12 12 12
12 55 44 18 18 18 18 18
42 12 55 44 42 42 42 42
94 42 18 55 44 44 44 44
18 94 42 42 55 55 55 55
06 18 94 67 67 67 67 67
67 67 67 94 94 94 94 94
procedure ParnajaSort;
var
i:index;
x:item;
nechet:boolean;
obmen,j:integer;
begin
nechet:=true; j:=0;
repeat
obmen:=0;
if nechet then i:=1 else i:=2;
repeat
if (A[i].key > A[i+1].key) then
begin
x:=A[i]; A[i]:=A[i+1]; A[i+1]:=x;
obmen:=obmen+1;
end;
i:=i+2;
until (i>=n);
j:=j+1;
if nechet=true then nechet:=false else nechet:=true;
until(obmen=0) and (j>=2);
end;
. . , . , .
, , , . , , , , , .
. i=2 3 4 5 6 7 8
44 06 06 06 06 06 06 06
55 44 12 12 12 12 12 12
12 55 44 18 18 18 18 18
42 12 55 44 42 42 42 42
94 42 18 55 44 44 44 44
18 94 42 42 55 55 55 55
06 18 94 67 67 67 67 67
67 67 67 94 94 94 94 94
. .
procedure BubbleSort;
var i,j: index; x: item;
begin for i:= 2 to n do
begin for j:= n downto i do
if (A[j-1].key > A[j].key) then
begin x:=A[j-1]; A[j-1]:=A[j]; A[j]:=x;
end;
end;
end; {BubbleSort}
-
. , , . , - . , , . , , () . , k, . i. : , . , 12,18,42,44,55,67,94 06 , 94,06,12,18,42,44,55,67 . : . -. , .
- .
procedure ShakeSort;
var j,k,l,r: index; x: item;
begin l:=2; r:=n; k:=n;
repeat
for j:=r downto l do
if (A[j-1].key > A[j].key) then
begin x:=A[j-1]; A[j-1]:=A[j]; A[j]:=x;
k:=j;
end;
l:=k+1;
for j:=l to r do
if (A[j-1].key > A[j].key) then
begin x:=A[j-1]; A[j-1]:=A[j]; A[j]:=x;
k:=j;
end;
r:=k-1;
until (l>r);
end; {ShakeSort}
i = 2 3 3 4 4
r = 8 8 7 7 4
^ v ^ v ^
44 06 06 06 06
55 44 44 12 12
12 55 12 44 18
42 12 42 18 42
94 42 55 42 44
18 94 18 55 55
06 18 67 67 67
67 67 94 94 94
, , .
, x1, x2, , xn
xi=(xi,p,xi,p-1,,xi,1)
, ..
xi=(xi,p,xi,p-1,,xi,1)<(xj,p,xj,p-1,,xj,1)=xj
, t≤p xi,l = xj,l l>t xi,t<xj,t. , 0≤xi,l<r, , r, p r- . , .
, l, l-1, , 1, , p, p-1,, l+1 , , . ; , , 76- 80- , 80- , 79- .. 76- . , , . , ; . .
, , , . , , xi LINKi; Q. Q0,Q1,,Qr-1, . , , , Q. Q ; .. , Q.
LINKi,,LINKn x1,,xn Q
Q0,,Qr-1
X←Q
while Q do X=(xp,xp-1,,x1)
For j=1 to p do Qxj←X