o (stability) .
o , . , .
o . , , . 
, . ( ) .
. :
o , . , .
. .
o , , ( ), . . '' , . , . , , .
: , .
.
(. insertion sort) . , ( ), :
o ;
o ;
o , ;
o ( , );
o .
, , . , , ; .
:
const N=255; type array_type=array [1..N] of integer; procedure InsertSort(var x:array_type); var i, j, buf:integer; begin for i:=1 to N do begin buf:=x[i]; j:=i-1; while (j>=0) and (x[j]>buf) do begin x[j+1]:=x[j]; j:=j-1; end; x[j+1]:=buf; end; end;, () . , , , 1000.
|
|
|
, n 0 k − 1. .
. C[0..k], , A, A[i] C[A[i]] . C, A j C[j] .
1:
{ 10 -. } for i:= 1 to 10 do beginc:= 0; {- -} p:= 0; { -} for j:= 1 to 10 do beginif a[i] > a[j] then begininc(p);end; { . } if (a[i] = a[j]) and (i <> j) then begininc(c);end; end; { j}{ - -} if c > 0 then beginfor p + 1 to (p + 1) + c dob[p]:= a[i];end; b[p + 1]:= a[i];end; { i}2:
for i:= 1 to n do begin c[a[i]]:= c[a[i]] + 1;end; {} p:= 1;for i:= 1 to n do begin for j:= 1 to c[i] do begin a[p]:= i; inc(p); end;end;: , :
| 1, 11 | , , . , , , . , . |
| 2, 12 | , , . , , , . . |
| 3, 13 | , , . , , , . . |
| 4, 14 | , , . , , , . . |
| 5, 15 | , , . , , , . . |
| 6, 16 | , , . , , , . . |
| 7, 17 | , , . , , , . . |
| 8, 18 | , , . , , , . . |
| 9, 19 | . , , , . , , . |
| 10, 20 | . , , , . , , . |
:
|
|
|
1. .
2. .
3. .
; .
