11.12 練習¶

11.12.1 知識鞏固¶

給定陣列 [4, 2, 5, 1, 3]，以下都按從小到大排序。

參考答案

前兩輪為：

輪次陣列狀態說明

1 [1, 2, 5, 4, 3] 最小元素 1 與首位交換

2 [1, 2, 5, 4, 3] 數值 2 已位於索引 1，無須交換

此時前兩個位置已經確定，後續只需在 [5, 4, 3] 中繼續選擇最小元素。
依次比較相鄰元素：4 與 2 交換、4 與 5 不換、5 與 1 交換、5 與 3 交換，得 [2, 4, 1, 3, 5] ，共 3 次交換；最大元素 5 已移動到陣列末尾，因此最後一個位置已經確定。

陣列 \([2_a, 2_b, 1]\) 中，\(2_a\) 和 \(2_b\) 的數值相同，但用下標標出了原有次序。

參考答案

選擇排序第一輪選出最小元素 1，並與首位 \(2_a\) 交換，得 \([1, 2_b, 2_a]\) 。\(2_a\) 被換到了 \(2_b\) 之後，兩者的相對次序已經改變。
泡沫排序先比較 \(2_a\) 和 \(2_b\)，因為兩者相等，不交換；再比較 \(2_b\) 和 1 並交換，第一輪結束後為 \([2_a, 1, 2_b]\) 。\(2_a\) 仍在 \(2_b\) 之前，相對次序沒有改變。
這個例子中，選擇排序會改變相等元素的原有次序；泡沫排序只在左邊元素大於右邊元素時交換相鄰元素。相等元素之間不交換，因此能保持它們原有的先後次序。

學校要排序許多固定為 8 位的學號。請回答：

參考答案

學號有 8 個數位，因此從最低位到最高位共處理 8 輪；每輪只按 0～9 分組。
直接計數需要為所有可能的 8 位取值預留位置，但實際學生只使用其中很少一部分，大多數計數位置會一直為 0。
應選擇基數排序。它利用了“位數固定、每位只有 10 種取值”的特點，只需重複 8 輪穩定分組。計數排序若把整個 8 位學號當作整數下標，則需要為大量實際不會出現的數值預留計數位置。

給定一個整數陣列 nums，請自行實現合併排序，把其中的元素按非遞減順序排列並返回。不要呼叫語言自帶的排序函式。

解題提示

給定整數陣列 nums 和非負整數 \(K\)，陣列中的每個元素都在 \(0\) 到 \(K\) 之間。

請實現計數排序，把結果按非遞減順序寫回 nums 並返回 nums。不要使用元素之間的大小比較來決定順序，也不要呼叫語言自帶的排序函式。

解題提示

輪次	陣列狀態	說明
1	`[1, 2, 5, 4, 3]`	最小元素 1 與首位交換
2	`[1, 2, 5, 4, 3]`	數值 2 已位於索引 1，無須交換