3
220100 ()
, 2009
1. .. 3
2. . 3
. 4
. 3
. 5
. 8
. 8
. 9
.. 10
3. . 11
4. . 11
5. . 24
.
, / - .
: . . , .
"" "" - . , , ...
, . , .
:
i- 0 size 1
j- size-1 i 1
a[j-1] > a[j],
x = a[j-1]
a[j-1] = a[j]
a[j] = x
j-
i-
: O(n2), , .
, .
, . n , (n-1)-.
i- a[i]... a[n] a[i]. n=5 .
i, a[0]...a[i] ( ) . , (n-1)- , a[n] , a[n] : . :
i- 0 size 1
k = i
x = a[i]
j- i + 1 size 1
a[j] < x,
k = j
x = a[j]
|
|
|
j-
a[k] = a[i]
a[i] = x
i-
n+1 n . , , :
n + (n-1) + (n-2) + (n-3) +... + 1 = 1/2 * (n2+n) = O(n2)
, , .
: " ".
- .
, ...
, i- a[0]...a[i] . : a[0]...a[i] . (. ) .
, i- . , : a[0]...a[i] a[i+1]...a[n].
, (i+1)- a[i+1] .
, .
( ), .
, x , ,
1. , x
2. .
:
i- 0 size 1
x = a[i]
j- i-1 (j >= 0 a[j] > x) -1
a[j+1] = a[j]
j-
a[j+1] = x
i-
, , O(n2), .
: . , , .
, . .
, , . :
i = 0 N-1
k = 0
j = 0 N-1
A(i) > A(j) A(i) = A(j) j < i,
k = k +1
-
- -j
B(k) = A(i)
- -i
, , , . B(k) , B(k). , k A(i) , , , A(i). , , A(i).
|
|
|
, . ( ) , .
, .
.
, 5 15 , 0 5. .
.
, , .
lowerBound upperBound , , , . . , , . , upperBound (M 1) . , . , , , . , 6, , .
- . , , 1023, 511 , - 255. , 1023 10 .
:
lowerBound = 0
upperBound = size
M = (lowerBound + upperBound) / 2
K < A[M],
upperBound = M 1
K > A[M],
lowerBound = M + 1
, :, M
lowerBound > upperBound,
:
1. size
2. K ,
3. .
3 . 15 , . .
Random:
Random Rnd = new Random();
Next Random :
int maxValue = 100;
int[] a = new int[1000];
for (int i = 0; i < 1000; i++)
a[i] = Rnd.Next(0, maxValue); // 0 100
