1學習目標
- 會做泡泡排序的一回合：相鄰比較，順序不對就交換。
- 會做選擇排序的一回合：找出最小值的位置，和最前面交換。
- 知道兩種排序法各是由哪些學過的技巧組合而成。
- （延伸）會把「一回合」重複做完，完成整個排序。
2概念說明
排序看起來很難，其實兩種經典方法都是前面學過的技巧組合起來的：
| 排序法 | 一回合在做什麼 | 用到的技巧 |
|---|---|---|
| 泡泡排序 | 從左到右，相鄰兩個比較，左邊比較大就交換 | K11 相鄰比較 ＋ K16 交換 |
| 選擇排序 | 找出最小值在哪裡，把它和最前面的交換 | K10 記住最小值的位置 ＋ K16 交換 |
泡泡排序一回合：大的數字會像泡泡一樣一路往右浮，一回合結束時，最大值一定到了最右邊。
5
1
4
2
3
↓ 5 ＞ 1，交換
1
5
4
2
3
↓ 一路比到最後
1
4
2
3
5
泡泡排序一回合後，最大的 5 到了最右邊
選擇排序一回合：在全部資料中選出最小的，換到第 1 個位置，第 1 個位置就確定了。
📌 為什麼先練「一回合」？
完整的排序就是把一回合重複做很多次。先把一回合寫對，再加一個外層迴圈重複它，就是完整的排序法（延伸挑戰）。
3示範題：跟著一步一步做（2 題）
先讀題，再一步一步點開來看。建議每看完一步，就先自己在平台上試著寫寫看。
相鄰交換一次
L2｜進階SORT01-003給定 N 個整數，請從左到右檢查每一組相鄰數字。如果左邊數字大於右邊數字，就交換兩者。整個清單只掃描一次。
- 輸入
- 第一個整數為 N，接著輸入 N 個整數。保證 N 大於或等於 2。
- 輸出
- 輸出掃描一次後的 N 個整數，中間以空白分隔。
範例1
輸入
輸入
5 5 1 4 2 3
輸出
1 4 2 3 5
第 1 步：讀題，找出輸入和輸出
- 輸入：N（至少 2），接著 N 個整數。
- 輸出：從左到右掃描一次、需要就交換之後的 N 個數字。
第 2 步：把問題拆成步驟
（讀入 N 個數字，存進 全部數字）
i 從 1 數到 N−1：
如果 第 i 項 ＞ 第 i＋1 項：
交換 第 i 項 和 第 i＋1 項
說出 全部數字（依序說出每一項）
迴圈只到 N−1，原因和 K11 一樣：最後一組是第 N−1 項和第 N 項。
第 3 步：用範例走一次
清單［5, 1, 4, 2, 3］：
| i | 比較 | 交換嗎？ | 這一步之後的清單 |
|---|---|---|---|
| 1 | 5 和 1 | 是 | 1 5 4 2 3 |
| 2 | 5 和 4 | 是 | 1 4 5 2 3 |
| 3 | 5 和 2 | 是 | 1 4 2 5 3 |
| 4 | 5 和 3 | 是 | 1 4 2 3 5 |
輸出「1 4 2 3 5」，最大值 5 到了最右邊。
第 4 步：對照範例答案
按「載入範例」，看看交換用的是 K16 的三個步驟，只是對象換成清單的第 i 項和第 i＋1 項。最後的說出可以用迴圈每一輪說出一項。
⚠️ 常見錯誤
- 迴圈跑到 N：最後一輪會拿不存在的第 N＋1 項來比。
- 掃描超過一次：題目只要一回合，多做幾回合結果會變成完全排好，反而不對。
選擇排序第一回合
L2｜進階seclect-004小安正在學習「選擇排序法」，老師請他先完成第一回合的任務。
桌上有一排固定 5 個的數字，依序放在第 1 到第 5 個位置中。
請你找出這 5 個數字中最小的數字，並把它與第 1 個位置的數字交換。
注意事項：
1. 只進行「第一回合」，不需要完成整個排序。
2. 若最小值有多個，請選擇最前面出現的那一個。
3. 交換完成後，其餘位置的數字順序保持不變
- 輸入
- 第1行：輸入一個整數N，N固定為5 第2行：輸入5 個整數，代表清單中第 1 到第 5 個位置的數字（以空格隔開）。
- 輸出
- 輸出 5 個整數，代表完成「選擇排序第一回合」後的數字順序（以空格隔開）。
範例1
輸入
輸入
5 8 3 5 1 6
輸出
1 3 5 8 6
範例2
輸入
輸入
5 2 4 6 8 10
輸出
2 4 6 8 10
第 1 步：讀題，找出輸入和輸出
- 輸入：N（固定為 5），接著 5 個整數。
- 輸出：把最小值和第 1 個位置交換之後的 5 個數字。
第 2 步：把問題拆成步驟
先用 K10 的方法找出最小值的位置，再和第 1 項交換：
（讀入 N 個數字，存進 全部數字）
最小位置 設為 1
j 從 2 數到 N：
如果 第 j 項 ＜ 第 最小位置 項：
最小位置 設為 j
交換 第 1 項 和 第 最小位置 項
說出 全部數字第 3 步：用範例走一次
清單［8, 3, 5, 1, 6］：最小位置從 1（值 8）開始，j ＝ 2 時 3 ＜ 8，最小位置變 2；j ＝ 4 時 1 ＜ 3，最小位置變 4。最後把第 1 項（8）和第 4 項（1）交換，得到「1 3 5 8 6」。
第 4 步：對照範例答案
按「載入範例」，範例答案比較的是「第 j 項」和「第 最小位置 項」，而不是另外存一個最小值變數，兩種寫法都可以。
⚠️ 常見錯誤
- 只記住最小值，沒記住位置：知道最小的是 1，卻不知道它在第幾格，就沒辦法交換。
- 比較時用 ≤：最小值出現多次時要選最前面那一個，所以要用「＜」。
4延伸挑戰（3 題）
核心題都會了嗎？這些題目需要把好幾個技巧組合起來，想挑戰的話可以試試看。
🚀 泡泡排序升冪 L3｜挑戰
挑戰重點：把示範 SORT01-003 的「一回合」外面再包一層「重複 N−1 次」，就是完整的泡泡排序。為什麼是 N−1 回合？每一回合都會把剩下的最大值推到最右邊，N 個數字做完 N−1 回合，只剩最前面一個，自然就排好了。按「載入範例」可以看到，範例答案就是在一回合的迴圈外面多包了一層「重複」。
給定 N 個整數，請使用泡泡排序法將它們由小到大輸出：從左到右比較相鄰的兩個數字，左邊比較大就交換，這樣掃描一回合；重複 N−1 回合就能全部排好。
- 輸入
- 第一個整數為 N，接著輸入 N 個整數。
- 輸出
- 輸出由小到大排序後的 N 個整數，中間以空白分隔。
範例1
輸入
輸入
5 5 1 4 2 3
輸出
1 2 3 4 5
💡 需要提示嗎？
把「掃描一回合」重複做 N-1 次，就是完整的泡泡排序。
🚀 完整選擇排序 L3｜挑戰
挑戰重點：把示範 seclect-004 的一回合重複做：第 k 回合從第 k 個位置找到最後，找出最小值的位置，和第 k 個位置交換。k 從 1 做到 N−1 就排好了。
小安已經學會如何在清單中找出最小值，並進行兩數交換。
現在老師請他完成完整的選擇排序任務。
桌上有一排固定 5 個整數，請你使用「選擇排序法」，
將這些數字由小到大排序。
選擇排序說明：
1. 從尚未排序的部分中找出最小值。
2. 將最小值與目前排序位置的數字交換。
3. 重複上述步驟，直到整個清單排序完成。
注意事項：
1. 不可使用排序相關的積木或指令。
2. 若有相同數字，排序後相對位置不限
- 輸入
- 第1行：輸入數字N，N固定為5 第2行：輸入5 個整數，代表清單中的數字（以空格隔開）。
- 輸出
- 輸出 5 個整數，代表排序完成後的結果（以空格隔開）。
範例1
輸入
輸入
5 8 3 5 1 6
輸出
1 3 5 6 8
範例2
輸入
輸入
5 2 4 6 8 10
輸出
2 4 6 8 10
💡 需要提示嗎？
第 k 回合從第 k 個位置之後找出最小值，再和第 k 個位置交換，重複到最後。
🚀 排序後的中間值 L3｜挑戰
挑戰重點：先用任何一種排序法把數字由小到大排好，中間值就在第（N＋1）÷ 2 個位置。例如 5 個數字，中間值是第 3 個。
給定奇數個整數，請將它們由小到大排序後，輸出中間位置的數字。位置從 1 開始計算。
- 輸入
- 第一個整數為 N，接著輸入 N 個整數。保證 N 為奇數。
- 輸出
- 輸出一個整數，代表排序後的中間值。
範例1
輸入
輸入
5 9 1 5 3 7
輸出
5
💡 需要提示嗎？
先把數字由小到大排好，中間值就在第 (N+1)/2 個位置。
5自我檢核
學完之後，檢查看看你能不能做到這些事。有做不到的，就回到上面對應的地方再看一次。
- 我會寫出泡泡排序的一回合，並知道一回合後最大值會到最右邊。
- 我會寫出選擇排序的一回合，並知道要先找出最小值的位置。
- 我能說出兩種排序法各是由哪些學過的技巧組合起來的。
- 我知道怎麼把一回合重複，變成完整的排序。