103年普考程式設計概要
|
三、假設書架上有七本書，已知每一本書的高度都不一樣，請以下列方式進行排序：第一個與第二個位置上的書先比較，較低的書放到第一個位置，較高的書放到第二個位置；再來第二個與第三個位置的書相比較，依此類推。第一輪做完後，再從頭開始進行第二輪的比較與交換，然後再進行第三輪、第四輪等，直至第六輪結束為止。 (一)若這七本書高度分別為15, 12, 17, 18, 11, 14, 19，請問每一輪需交換書本位置的次數為何？（10分） (二)若總共有 n 本書本，最多共需交換幾次書本才能排序完成？（5分） (三)請宣告並說明如何以一維陣列 books[n] 來表示書本的位置與高度。（5分） (四)請以上述宣告的一維陣列資料結構為基礎，用 C, C++ 或 Java 寫出上述排序演算法。（10分） |
答：
(一)
1.第一輪：
|
起始值 |
15 |
12 |
17 |
18 |
11 |
14 |
19 |
|
第一回 |
12 |
15 |
17 |
18 |
11 |
14 |
19 |
|
第二回 |
12 |
15 |
17 |
18 |
11 |
14 |
19 |
|
第三回 |
12 |
15 |
17 |
18 |
11 |
14 |
19 |
|
第四回 |
12 |
15 |
17 |
11 |
18 |
14 |
19 |
|
第五回 |
12 |
15 |
17 |
11 |
14 |
18 |
19 |
|
第六回 |
12 |
15 |
17 |
11 |
14 |
18 |
19 |
12和15交換，11和18交換，以及14和18交換，所以交換3次。
2.第二輪：
|
起始值 |
12 |
15 |
17 |
11 |
14 |
18 |
19 |
|
第一回 |
12 |
15 |
17 |
11 |
14 |
18 |
19 |
|
第二回 |
12 |
15 |
17 |
11 |
14 |
18 |
19 |
|
第三回 |
12 |
15 |
11 |
17 |
14 |
18 |
19 |
|
第四回 |
12 |
15 |
11 |
14 |
17 |
18 |
19 |
|
第五回 |
12 |
15 |
11 |
14 |
17 |
18 |
19 |
17和11交換，14和17交換，所以交換2次。
3.第三輪：
|
起始值 |
12 |
15 |
11 |
14 |
17 |
18 |
19 |
|
第一回 |
12 |
15 |
11 |
14 |
17 |
18 |
19 |
|
第二回 |
12 |
11 |
15 |
14 |
17 |
18 |
19 |
|
第三回 |
12 |
11 |
14 |
15 |
17 |
18 |
19 |
|
第四回 |
12 |
11 |
14 |
15 |
17 |
18 |
19 |
15和11交換，15和14交換，所以交換2次。
4.第四輪：
|
起始值 |
12 |
11 |
14 |
15 |
17 |
18 |
19 |
|
第一回 |
11 |
12 |
14 |
15 |
17 |
18 |
19 |
|
第二回 |
11 |
12 |
14 |
15 |
17 |
18 |
19 |
|
第三回 |
11 |
12 |
14 |
15 |
17 |
18 |
19 |
12和11交換，所以交換1次。
5.第五輪：
|
起始值 |
11 |
12 |
14 |
15 |
17 |
18 |
19 |
|
第一回 |
11 |
12 |
14 |
15 |
17 |
18 |
19 |
|
第二回 |
11 |
12 |
14 |
15 |
17 |
18 |
19 |
沒有交換，所以交換0次。
6.第六輪：
|
起始值 |
11 |
12 |
14 |
15 |
17 |
18 |
19 |
|
第一回 |
11 |
12 |
14 |
15 |
17 |
18 |
19 |
沒有交換，所以交換0次。
(二)
(n-1)+(n-2)+(n-3)+…+1 =
。
(三)
可以宣告為 int books[n];
books[0] = 15，索引0是指第一本書，它的值15是指第一本書的高度。
books[1] = 12，索引1是指第二本書，它的值12是指第二本書的高度。
…
books[n] = k，索引 n 是指第 n+1 本書，它的值 k 是指第 n+1 本書的高度。
(四)
|
#include <stdio.h> void printData(int data[], int n) { for (int i = 0; i < n; i++) { if (i == n - 1) { // 印出最後一個元素 printf("%d", data[i]); } else { printf("%d, ", data[i]); } } printf("\n"); } // 泡沫排序法 void Bubble_Sort(int a[], int n) { // a[ ] 是想要排序的陣列，n 是陣列大小 int i, j, temp; for (i = n - 1; i > 0; i--) { for (j = 0; j < i; j++) { if (a[j] > a[j + 1]) { // 相鄰兩個元素比較，左大右小則交換 temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } printData(a, n); } } int main(void) { int data[] = { 15, 12, 17, 18, 11, 14, 19 }; printData(data, sizeof(data) / sizeof(int)); Bubble_Sort(data, sizeof(data) / sizeof(int)); return 0; } |
執行結果：
15, 12, 17, 18, 11, 14, 19
12, 15, 17, 11, 14, 18, 19
12, 15, 11, 14, 17, 18, 19
12, 11, 14, 15, 17, 18, 19
11, 12, 14, 15, 17, 18, 19
11, 12, 14, 15, 17, 18, 19
11, 12, 14, 15, 17, 18, 19
留言列表
國考資訊處理解答 (7)
