Learning Objectives
- 說明選擇排序、插入排序、氣泡排序各自怎麼把資料排好
- 數出排序的比較次數與交換（移動）次數，說明三者的最壞情況都是 O(n²)
- 說明氣泡排序怎麼提早結束，以及插入排序為什麼在幾乎排好的資料上很快
- 說明什麼是穩定排序，判斷三種排序是否穩定
把資料排好順序
成績由高到低列出、商品依價格排列、檔案依修改時間排序：排序（sorting）幾乎是每個程式都會用到的工作。 第 04 課也看到，資料排好之後才能用二分搜尋，從 O(n) 變成 O(log n)。
這一課介紹三種最直觀的排序。它們都只用兩種基本操作：
- 比較：兩個元素誰大誰小
- 交換（或搬移）：把元素放到另一個位置
所以衡量一個排序快不快，就是數它做了幾次比較、幾次交換。這一課的範例都會把這兩個數字算出來，放在動畫上方。
三種排序都是原地排序（in-place）：直接在原本的陣列裡調整，只多用幾個變數。
選擇排序：每一輪挑出最小的
整理一疊考卷時，你可能會先翻一遍找出分數最低的，放到最前面；再從剩下的找最低的，放到第二個……這就是選擇排序（selection sort）：
- 第 i 輪（i 從 0 開始），在
a[i]到最後之間找出最小值的位置min_idx - 把它和
a[i]交換；這樣a[0]～a[i]就排好了 - 做完 n - 1 輪，整個陣列就排好了
不管資料長什麼樣子，第 i 輪都要把後面的 n - 1 - i 個全部看過，所以比較次數一定是 (n-1) + (n-2) + … + 1 = n(n-1)/2。 交換很少：每一輪最多一次，全部最多 n - 1 次。
選擇排序：找最小值，換到前面
看 min 指標：j 每往右走一格就比一次，遇到更小的值 min 就跳過去。一輪結束才交換一次。7 個元素一定比較 6 + 5 + 4 + 3 + 2 + 1 = 21 次；這份資料只需要交換 4 次。
插入排序：像整理手上的牌
打牌時一張一張拿起來，每拿一張就插進手上已經排好的牌裡適當的位置，這就是插入排序（insertion sort）：
- 把
a[0]看成已經排好的一小段 - 第 i 輪拿起
key = a[i]，往左邊看：比 key 大的往右挪一格，直到遇到不比 key 大的元素（或到了最左邊） - 把 key 放進空出來的位置；
a[0]～a[i]就排好了
和選擇排序不同，插入排序遇到「不比 key 大」的元素就停，所以資料越接近排好，比較次數越少：
| 資料 | 比較次數 | 移動次數 |
|---|---|---|
| 已經排好 | n - 1（每輪比一次就停） | 0 |
| 完全反向 | n(n-1)/2 | n(n-1)/2 |
下面的範例用同一個函式排兩份資料：一份是亂序，一份是只有兩個元素位置相反的「幾乎排好」。
插入排序：亂序與幾乎排好的資料
比 key 大的元素一格一格往右挪，挪的過程中會暫時出現兩個相同的值，那是正常的：key 還拿在手上，最後才放回去。亂序資料比較 16 次、移動 12 次；幾乎排好的資料只比較 7 次、移動 1 次。j 走到 -1 時表示已經到最左邊，標在格子下方的文字裡。
氣泡排序：相鄰的兩個比，順序不對就換
氣泡排序（bubble sort）只看相鄰的兩個元素：
- 從左到右，比較
a[j]和a[j + 1]，左邊比較大就交換 - 一輪走完，最大的元素會一路被換到最右邊，像氣泡浮上水面；最後一格就排好了
- 下一輪只要處理前面還沒排好的部分，第 i 輪只比到
n - 1 - i
提早結束：如果某一輪從頭到尾都沒有交換，表示每一對相鄰元素的順序都對，整個陣列已經排好，可以直接停止。
範例用一個變數 swapped 記錄這一輪有沒有交換過。有了這個判斷，已經排好的資料只要一輪、比較 n - 1 次就結束；沒有的話一定要做滿 n - 1 輪。
氣泡排序：一輪沒有交換就停
這份資料只有前面三個順序亂掉。第 1 輪把 12 換到 3 的後面，第 2 輪把 5 換到 3 的後面，第 3 輪一次都沒交換，程式就停了：只比較 15 次。如果沒有提早結束，要做滿 6 輪、比較 21 次。
三種排序比一比
| 選擇排序 | 插入排序 | 氣泡排序（提早結束） | |
|---|---|---|---|
| 最好情況（已排好）的比較次數 | n(n-1)/2 | n - 1 | n - 1 |
| 最壞情況（反向）的比較次數 | n(n-1)/2 | n(n-1)/2 | n(n-1)/2 |
| 交換（移動）次數 | 最多 n - 1 | 最多 n(n-1)/2 | 最多 n(n-1)/2 |
| 時間複雜度（最壞） | O(n²) | O(n²) | O(n²) |
| 額外空間 | O(1) | O(1) | O(1) |
三種排序最壞都是 O(n²)：資料變成 10 倍，比較次數大約變成 100 倍。一萬筆資料要比較約五千萬次，一百萬筆就要約五千億次，所以實際上大量資料不會用它們。 不過它們各有用處：選擇排序的交換次數最少，適合「搬動很貴、比較很便宜」的情況；插入排序在資料幾乎排好或很少筆時非常快， 很多語言的內建排序在資料切到很小時，就改用插入排序處理（例如 Python 的 Timsort 會用插入排序處理小段資料）。
下面的小工具讓三種排序在同一份資料上賽跑。改變資料型態，看看誰先跑完、各做了幾次比較與交換。
想一想：比較與交換的次數
用本課的選擇排序排一份已經排好的資料，下面的程式會印出什麼？
a = [1, 2, 3, 4, 5]
n = len(a)
comparisons = swaps = 0
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
comparisons += 1
if a[j] < a[min_idx]:
min_idx = j
if min_idx != i:
a[i], a[min_idx] = a[min_idx], a[i]
swaps += 1
print(comparisons, swaps)
有提早結束判斷的氣泡排序，排一份 100 個元素、已經排好的資料，要比較幾次？
用本課的插入排序排 [6, 5, 4, 3, 2, 1]（完全反向），下面的程式印出的移動次數是多少？
a = [6, 5, 4, 3, 2, 1]
shifts = 0
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
shifts += 1
j -= 1
a[j + 1] = key
print(shifts)
穩定排序：同分的人，順序會不會亂掉
報名表依報名順序排好了，現在要依分數由低到高重排。分數相同的兩個人，誰該排前面？
穩定排序（stable sort）保證：鍵值相同的元素，排序後仍然維持原本的先後順序。 這在「先依一個欄位排、再依另一個欄位排」時很重要： 例如先依姓名排好，再用穩定排序依分數排，同分的人就會照姓名順序排列。
- 插入排序是穩定的：只有左邊的元素「嚴格大於」key 才往右挪，遇到相等的就停下來，key 不會越過同分的元素
- 氣泡排序是穩定的：只有
a[j] > a[j + 1]才交換，相等的相鄰元素不會互換 - 選擇排序不穩定：它會把遠處的最小值和
a[i]直接交換，原本在a[i]的元素可能被丟到同分元素的後面
下面的範例有四個人：甲 80、乙 70、丙 80、丁 60。甲和丙同分，甲原本在前面。分數和名字放在兩個平行的陣列裡，交換時兩個陣列一起換。
穩定性：選擇排序讓同分的甲、丙換了順序
選擇排序第一輪找到最小的丁 60，把它和第一個位置的甲 80 直接交換，甲一下子被丟到丙的後面，之後再也不會換回來。插入排序排同一份資料，甲仍然在丙的前面。
想一想：穩定性
照本課的寫法，哪些排序是穩定的？
把插入排序的判斷從「a[j] <= key 就停」改成「a[j] < key 才停」（也就是相等時也往右挪），結果會怎樣？
實作：插入排序的每一輪
請完成插入排序的內層迴圈：把比 key 大的元素往右挪，再把 key 放進空出來的位置。程式會印出每一輪結束時的陣列。預期輸出在右邊；可以切換成你熟悉的語言。
重點整理
- 選擇排序：每一輪找出剩下的最小值，換到前面。比較次數固定 n(n-1)/2，交換最多 n - 1 次；不穩定
- 插入排序：一個一個拿起來，插進左邊已經排好的部分。已排好的資料只比 n - 1 次，反向資料比 n(n-1)/2 次；穩定
- 氣泡排序：相鄰兩個順序不對就交換，最大值每輪浮到最後；加上「一輪沒交換就停」可以提早結束；穩定
- 三種的最壞情況都是 O(n²)，額外空間都是 O(1)
- 穩定排序：鍵值相同的元素維持原本的先後順序，多欄位排序時很重要
下一課：合併排序。把陣列切成兩半，各自排好再合併，最壞情況也只要 O(n log n)。