, .
.
.
. , , . N-1 .
A, A[1], A[2],..., A[n] for (i:=1; i <= N-1; i++){
for(j:=1; j <= N-i; j++)
{
if(A[j] > A[j+1])
{
Temp:=A[j];
A[j]:=A[j+1];
A[j+1]:=Temp;
}
}
}
O(n2).
.
, , . .
A, A[1], A[2],..., A[n] for (i:=2; i <= n; i++) { key:= A[i]; j:= i 1; while(j >= 1) { if(A[j] > key) { A[j + 1]:= A[j]; A[j]:= key; } j:= j 1; }}
. . n-1, .. O(n).
, . A[0], i . ( n ) . O(n2).
.
. .
:
1. ;
2. ;
3. .
:
, .. a , .
, .
.
:
.
. :
. . . - .
|
|
, . :
, , . log(n). , . .
.
n. x ( ). x , . x , x :
, , .
:
QuickSort(A[], l, r)
{
if(l ≥ r) return;
m=Partition(A[], l, r);
QuickSort(A[], l, m-1);
QuickSort(A[], m+1, r);
}
Partition , , .
Partition(A[], l, r)
{
i:= l-1;
for(j= l; j ≤ r; j=j+1)
{
if(A[j] ≤ A[r])
{
temp:= A[i+1];
A[i+1]:= A[j];
A[j]:= temp;
i:= i+1;
}
}
return i;
}
. , . :
, (), :
, . , . . . .