兩個最好懂的 O(n²) 排序 —— 選擇排序每趟挑最小,插入排序像整理手上的撲克牌。
O(n²),適合小資料或入門教學。選擇排序:每一趟從沒排好的裡面挑出最小的,放到最前面。插入排序:像打牌時整理手牌,把每張新牌插進左邊已排好的正確位置。它們慢,但簡單、就地、好懂 —— 而且插入排序還是很多高效排序的「基礎零件」。
每趟找最小 —— 在「還沒排好」的區段裡找出最小值。
換到最前 —— 把它跟該區段的第一格交換,那格就定位了。
重複縮小 —— 已排好的區段每趟長一格,直到全部排完。
特點 —— 交換次數少(最多 n-1 次),但比較次數固定 n²/2;就算資料已經排好也一樣慢。
像整理手牌 —— 左邊維持一段「已排好」的,每次拿右邊下一張。
找位置插入 —— 這張牌往左比,比它大的都右移一格,騰出空位插進去。
越排越長 —— 已排好的區段一格格變長,直到最後一張插完。
特點 —— 資料接近排好時超快(接近 O(n)),而且穩定。這是它比選擇排序好用的地方。
共同點 —— 都是 O(n²)、都就地(不佔額外空間)、都最好懂。
選擇排序 —— 比較次數固定、交換最少;但不穩定、也不會因資料而變快。「寫入昂貴」時才略有優勢。
插入排序 —— 接近排好時接近 O(n)、穩定;實務更常用,還是 Timsort 等混合排序在「小片段」時的基礎零件。
提醒 —— 兩個都只適合小資料(幾十~幾百筆)。大資料請用合併 / 快速排序,或直接 sorted()。
n²/2。每摸一張新牌,就把它插進手上已經排好的正確位置,大的往右挪。
從還沒排的人裡挑出最矮的,站到隊伍最前面,一個一個定位。
已經照高矮排好的書架,新書拿來就往左比,插進剛好的縫。
同一組數字 [5, 2, 8, 3, 1, 6],切換兩種排序看差別。紫色是正在比較 / 選中的、紅色是剛被放定位的、綠色是已排好的區段。按「下一步」一步步走。
兩種排序的基本寫法、由大到小、穩定性、交換次數、二分插入,以及為什麼插入排序是混合排序的零件。
❌ 拿它們排大資料 —— O(n²) 在幾萬筆就慢到爆,用合併 / 快速 / 內建 sorted()。
❌ 以為選擇排序「已排好就會快」 —— 不會,它比較次數固定,永遠 O(n²)。會因資料變快的是插入排序。
❌ 插入排序寫成 >= 破壞穩定性 —— 要用 >,相同鍵才會維持原順序。
❌ 選擇排序把交換寫在內層 —— 交換要在「找完最小之後」做一次,不是每次比較都換(那就退化成低效氣泡)。
[3, 1, 2] 做選擇排序,列出每一趟結束後的陣列。做插入排序呢?把答案打到對話裡,我幫你對。