:
- ()
, , . , , , .
, . , . , ; .
, . , . , .
. ( ), :
, ;
, ;
( , );
;
- : O(n ²)
, , , .
, , . ; . ( ), .
: , . . , , , , . θ(n²).
java
public void addingSort() {
for (Node cur = first.next; cur!= null; cur = cur.next) {
Node n = cur.prev;
Object val = cur.value;
for (; n!= null; n = n.prev) {
if (((Comparable) n.value).compareTo(val) > 0) {
n.next.value = n.value;
} else {
break;
}
}
if (n!= null) {
n.next.value = val;
} else {
first.value = val;
}
}
}
. . . , . , dcab :
|
|
|
d c a b
1 c d a b
2 a c d b
3 a b c d
. n - 1 , .. . , dcab, :
d c a b 1 a c d b 2 a b d c 3 a b c d
, , n - 1 , n /2 . , 1/2(n 2- n) . , n 2, - . , , , .
java
public void SelectSort() {
Object c;
for (Node a = first; a!= last; a = a.next) {
Node min = last;
for (Node b = a; b!= last; b = b.next) {
if (((Comparable) b.val).compareTo(min.val) < 0) {
min = b;
}
}
c = a.val;
a.val = min.val;
min.val = c;
}
}
. . , .
, .. . (.. ) , , . .
, , , dcab. :
d c a b
1 a d c b
2 a b d c
3 a b c d
, , . , , , , . .
, for , . ,
(n 2- n)/2
, n . , n - 1 , n /2 . .
|
|
|
n 2 . , n 2, . , n 2 , .
, . n 2.
