P7
211275022田昊东¶
9.2¶
1直接插入排序¶
| 12 | 2 | 16 | 30 | 28 | 10 | 16 | 20 | 6 | 18 | 比较次数 |
|---|---|---|---|---|---|---|---|---|---|---|
| 2 | 12- | 16 | 30 | 28 | 10 | 16 | 20 | 6 | 18 | 1 |
| 2 | 12 | 16- | 30 | 28 | 10 | 16 | 20 | 6 | 18 | 1 |
| 2 | 12 | 16 | 30- | 28 | 10 | 16 | 20 | 6 | 18 | 1 |
| 2 | 12 | 16 | 28 | 30- | 10 | 16 | 20 | 6 | 18 | 1 |
| 2 | 10 | 12 | 16 | 28 | 30- | 16 | 20 | 6 | 18 | 5 |
| 2 | 10 | 12 | 16 | 16 | 28 | 30- | 20 | 6 | 18 | 3 |
| 2 | 10 | 12 | 16 | 16 | 20 | 28 | 30- | 6 | 18 | 3 |
| 2 | 6 | 10 | 12 | 16 | 16 | 20 | 28 | 30- | 18 | 8 |
| 2 | 6 | 10 | 12 | 16 | 16 | 18 | 28 | 30 | 18- | 4 |
- 1+1+1+1+5+3+3+8+4=27
2希尔排序¶
| 12 | 2 | 16 | 30 | 28 | 10 | 16 | 20 | 6 | 18 | 比较次数 |
|---|---|---|---|---|---|---|---|---|---|---|
| 10 | 2 | 16 | 30 | 28 | 12- | 16 | 20 | 6 | 18 | 1 |
| 10 | 2 | 16 | 30 | 28 | 12 | 16- | 20 | 6 | 18 | 1 |
| 10 | 2 | 16 | 30 | 28 | 12 | 16 | 20- | 6 | 18 | 1 |
| 10 | 2 | 16 | 6 | 28 | 12 | 16 | 20 | 30- | 18 | 1 |
| 10 | 2 | 16 | 6 | 18 | 12 | 16 | 20 | 30 | 28- | 1 |
| 10 | 2 | 16- | 6 | 18 | 12 | 16 | 20 | 30 | 28 | 1 |
| 10 | 2 | 16 | 30- | 28 | 12 | 16 | 20 | 6 | 18 | 1 |
| 10 | 2 | 16 | 30 | 28- | 12 | 16 | 20 | 6 | 18 | 1 |
| 10 | 2 | 16 | 12 | 28 | 30- | 16 | 20 | 6 | 18 | 2 |
| 10 | 2 | 16 | 12 | 16 | 30 | 28- | 20 | 6 | 18 | 2 |
| 10 | 2 | 16 | 12 | 16 | 20 | 28 | 30- | 6 | 18 | 2 |
| 6 | 2 | 10 | 12 | 16 | 20 | 16 | 30 | 28- | 18 | 4 |
| 6 | 2 | 10 | 12 | 16 | 18 | 16 | 20 | 28 | 30- | 3 |
| 2 | 6- | 10 | 12 | 16 | 18 | 16 | 20 | 28 | 30 | 1 |
| 2 | 6 | 10- | 12 | 16 | 18 | 16 | 20 | 28 | 30 | 1 |
| 2 | 6 | 10 | 12- | 16 | 18 | 16 | 20 | 28 | 30 | 1 |
| 2 | 6 | 10 | 12 | 16- | 18 | 16 | 20 | 28 | 30 | 1 |
| 2 | 6 | 10 | 12 | 16 | 18- | 16 | 20 | 28 | 30 | 1 |
| 2 | 6 | 10 | 12 | 16 | 16 | 18- | 20 | 28 | 30 | 2 |
| 2 | 6 | 10 | 12 | 16 | 16 | 18 | 20- | 28 | 30 | 1 |
| 2 | 6 | 10 | 12 | 16 | 16 | 18 | 20 | 28- | 30 | 1 |
| 2 | 6 | 10 | 12 | 16 | 16 | 18 | 20 | 28 | 30- | 1 |
- 共32
3起泡排序¶
| 12 | 2 | 16 | 30 | 28 | 10 | 16 | 20 | 6 | 18 | 比较次数 |
|---|---|---|---|---|---|---|---|---|---|---|
| 2- | 12 | 6 | 16 | 30 | 28 | 10 | 16 | 20 | 18 | 9 |
| 2 | 6- | 12 | 10 | 16 | 30 | 28 | 16 | 18 | 20 | 8 |
| 2 | 6 | 10- | 12 | 16 | 16 | 30 | 28 | 18 | 20 | 7 |
| 2 | 6 | 10 | 12- | 16 | 16 | 18 | 30 | 28 | 20 | 6 |
| 2 | 6 | 10 | 12 | 16- | 16 | 18 | 20 | 30 | 28 | 5 |
| 2 | 6 | 10 | 12 | 16 | 16- | 18 | 20 | 28 | 30 | 4 |
| 2 | 6 | 10 | 12 | 16 | 16 | 18- | 20 | 28 | 30 | 3 |
- 共42
4快速排序¶
| 12 | 2 | 16 | 30 | 28 | 10 | 16 | 20 | 6 | 18 | 比较次数 |
|---|---|---|---|---|---|---|---|---|---|---|
| 2 | 10 | 6 | 12- | 16 | 30 | 28 | 16 | 20 | 18 | 9 |
| 2- | 10 | 6 | 12 | 16- | 30 | 28 | 16 | 20 | 18 | 7 |
| 2 | 6 | 10- | 12 | 16 | 28 | 16 | 20 | 18 | 30- | 5 |
| 2 | 6 | 10 | 12 | 16 | 16 | 20 | 18 | 28- | 30 | 3 |
| 2 | 6 | 10 | 12 | 16 | 16- | 20 | 18 | 28 | 30 | 2 |
| 2 | 6 | 10 | 12 | 16 | 16 | 18 | 20- | 28 | 30 | 1 |
- 共27
5直接选择排序¶
| 12 | 2 | 16 | 30 | 28 | 10 | 16 | 20 | 6 | 18 | 比较次数 |
|---|---|---|---|---|---|---|---|---|---|---|
| 2- | 12 | 16 | 30 | 28 | 10 | 16 | 20 | 6 | 18 | 9 |
| 2 | 6- | 16 | 30 | 28 | 10 | 16 | 20 | 12 | 18 | 8 |
| 2 | 6 | 10- | 30 | 28 | 16 | 16 | 20 | 12 | 18 | 7 |
| 2 | 6 | 10 | 12- | 28 | 16 | 16 | 20 | 30 | 18 | 6 |
| 2 | 6 | 10 | 12 | 16- | 28 | 16 | 20 | 30 | 18 | 5 |
| 2 | 6 | 10 | 12 | 16 | 16- | 28 | 20 | 30 | 18 | 4 |
| 2 | 6 | 10 | 12 | 16 | 16 | 18- | 20 | 30 | 28 | 3 |
| 2 | 6 | 10 | 12 | 16 | 16 | 18 | 20- | 30 | 28 | 2 |
| 2 | 6 | 10 | 12 | 16 | 16 | 18 | 20 | 28 | 30 | 1 |
- 比较45次
6锦标赛排序¶
| 12 | 2 | 16 | 30 | 28 | 10 | 16 | 20 | 6 | 18 | 比较次数 |
|---|---|---|---|---|---|---|---|---|---|---|
| 2- | 9 | |||||||||
| 2 | 6- | 4 | ||||||||
| 2 | 6 | 10- | 3 | |||||||
| 2 | 6 | 10 | 12- | 3 | ||||||
| 2 | 6 | 10 | 12 | 16- | 4 | |||||
| 2 | 6 | 10 | 12 | 16 | 16- | 4 | ||||
| 2 | 6 | 10 | 12 | 16 | 16 | 18- | 3 | |||
| 2 | 6 | 10 | 12 | 16 | 16 | 18 | 20- | 3 | ||
| 2 | 6 | 10 | 12 | 16 | 16 | 18 | 20 | 28- | 3 | |
| 2 | 6 | 10 | 12 | 16 | 16 | 18 | 20 | 28 | 30- | 3 |
- 总共比较39次
7堆排序¶
| 12 | 2 | 16 | 30 | 28 | 10 | 16 | 20 | 6 | 18 | 比较次数 |
|---|---|---|---|---|---|---|---|---|---|---|
| 30 | 28 | 16 | 20 | 18 | 10 | 16 | 2 | 6 | 12 | 12 |
| 28 | 20 | 16 | 12 | 18 | 10 | 16 | 2 | 6 | 30 | 4 |
| 20 | 18 | 16 | 12 | 6 | 10 | 16 | 2 | 28 | 30 | 4 |
| 18 | 12 | 16 | 2 | 6 | 10 | 16 | 20 | 28 | 30 | 4 |
| 16 | 12 | 16 | 2 | 6 | 10 | 18 | 20 | 28 | 30 | 2 |
| 16 | 12 | 10 | 2 | 6 | 16 | 18 | 20 | 28 | 30 | 2 |
| 12 | 6 | 10 | 2 | 16 | 16 | 18 | 20 | 28 | 30 | 2 |
| 10 | 6 | 2 | 12 | 16 | 16 | 18 | 20 | 28 | 30 | 2 |
| 6 | 2 | 10 | 12 | 16 | 16 | 18 | 20 | 28 | 30 | 1 |
| 2 | 6 | 10 | 12 | 16 | 16 | 18 | 20 | 28 | 30 |
- 总共比较33次
8二路归并排序¶
| 12 | 2 | 16 | 30 | 28 | 10 | 16 | 20 | 6 | 18 | 比较次数 |
|---|---|---|---|---|---|---|---|---|---|---|
| 2 | 12 | 16 | 28 | 30 | 10 | 16 | 20 | 6 | 18 | 4 |
| 2 | 12 | 16 | 28 | 30 | 10 | 16 | 20 | 6 | 18 | 4 |
| 2 | 12 | 16 | 28 | 30 | 6 | 10 | 16 | 18 | 20 | 7 |
| 2 | 6 | 10 | 12 | 16 | 16 | 18 | 20 | 28 | 30 | 8 |
- 共比较23次
4¶
-1
-
A
-
A B C D E A 0 3 2 5 4 B / 0 7 7 / C 5 / 0 -3 / D / -2 6 0 4 E -2 / / / 0 -
Path
-
A B C D E A / A A A A B / / B B / C C / / C / D / D D / D E E / / / /
A
-
A
-
A B C D E A 0 3 2 5 4 B / 0 7 7 / C 5 8 0 -3 9 D / -2 6 0 4 E -2 1 0 3 0 -
Path
-
A B C D E A / A A A A B / / B B / C C A / C A D / D D / D E E A A A /
B
-
A
-
A B C D E A 0 3 2 5 4 B / 0 7 7 / C 5 8 0 -3 9 D / -2 5 0 4 E -2 1 0 3 0 -
Path
-
A B C D E A / A A A A B / / B B / C C A / C A D / D B / D E E A A A /
C
-
A
-
A B C D E A 0 3 2 -1 4 B 7 0 7 4 16 C 5 8 0 -3 9 D 10 -2 5 0 4 E -2 1 0 -3 0 -
Path
-
A B C D E A / A A C A B C / B C A C C A / C A D C D B / D E E A A C /
D
-
A
-
A B C D E A 0 -3 2 -1 3 B 7 0 7 4 8 C 5 -5 0 -3 1 D 10 -2 5 0 4 E -2 -5 0 -3 0 -
Path
-
A B C D E A / D A C D B C / B C D C C D / C D D C D B / D E E D A C /
E
-
A
-
A B C D E A 0 -3 2 -1 3 B 6 0 7 4 8 C -1 -5 0 -3 1 D 2 -2 4 0 4 E -2 -5 0 -3 0 -
Path
-
A B C D E A / D A C D B E / B C D C E D / C D D E D A / D E E D A C /
5¶
- BDFACEH
