跳轉至
紙質書（簡體中文版）已發行，詳情請見這裡

# 11.12 練習

## 11.12.1 知識鞏固

### 1. 選擇排序和泡沫排序的前幾輪

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

1. 按選擇排序模擬前兩輪，寫出每輪結束後的陣列，並指出此時哪些位置已經確定。
2. 按泡沫排序模擬第一輪，寫出陣列狀態和交換次數，並指出哪個位置已經確定。

參考答案

1. 前兩輪為：

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

   此時前兩個位置已經確定，後續只需在 `[5, 4, 3]` 中繼續選擇最小元素。

2. 依次比較相鄰元素：4 與 2 交換、4 與 5 不換、5 與 1 交換、5 與 3 交換， 得 `[2, 4, 1, 3, 5]` ，共 3 次交換；最大元素 5 已移動到陣列末尾，因此最後一個位置已經確定。

### 2. 相同元素的先後次序會變嗎

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

1. 寫出選擇排序第一輪結束後的陣列。\(2_a\) 和 \(2_b\) 的相對次序是否改變？
2. 寫出泡沫排序第一輪結束後的陣列。\(2_a\) 和 \(2_b\) 的相對次序是否改變？
3. 根據前兩問，說明兩種排序在保持相等元素原有次序方面有什麼不同。

參考答案

1. 選擇排序第一輪選出最小元素 1，並與首位 \(2_a\) 交換，得 \([1, 2_b, 2_a]\) 。\(2_a\) 被換到了 \(2_b\) 之後，兩者的相對次序已經改變。

2. 泡沫排序先比較 \(2_a\) 和 \(2_b\)，因為兩者相等，不交換；再比較 \(2_b\) 和 1 並交換， 第一輪結束後為 \([2_a, 1, 2_b]\) 。\(2_a\) 仍在 \(2_b\) 之前，相對次序沒有改變。

3. 這個例子中，選擇排序會改變相等元素的原有次序；泡沫排序只在左邊元素大於右邊元素時 交換相鄰元素。相等元素之間不交換，因此能保持它們原有的先後次序。

### 3. 比較計數排序和基數排序

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

1. 從最低位開始的基數排序需要處理幾輪？
2. 如果把學號直接當作整數使用計數排序，為什麼會準備大量沒有用到的計數位置？
3. 根據前兩問，如果在計數排序和基數排序之間選擇一種處理大量固定為 8 位的學號，你會選擇哪一種？為什麼？

參考答案

1. 學號有 8 個數位，因此從最低位到最高位共處理 8 輪；每輪只按 0～9 分組。

2. 直接計數需要為所有可能的 8 位取值預留位置，但實際學生只使用其中很少一部分， 大多數計數位置會一直為 0。

3. 應選擇基數排序。它利用了“位數固定、每位只有 10 種取值”的特點，只需重複 8 輪穩定分組。 計數排序若把整個 8 位學號當作整數下標，則需要為大量實際不會出現的數值預留計數位置。

## 11.12.2 程式設計練習

### 1. 用合併排序排列陣列

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

解題提示

1. 區間長度不超過 1 時，它已經有序
2. 從中點把區間分成兩半，並分別遞迴排序
3. 用兩個指標合併兩個有序半區，再把結果寫回原陣列

LeetCode

### 2. 用計數排序排列整數陣列

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

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

解題提示

1. 因為每個元素都在 0 到 K 之間，可以直接用元素值作為計數陣列的索引
2. 第一遍掃描 nums，令對應位置的計數加 1
3. 再從 0 到 K 掃描計數陣列；數值 x 出現多少次，就向 nums 中連續寫入多少個 x

##### 歡迎在評論區留下你的見解、問題或建議