一疊亂序觀測記錄，怎樣排得又對又省事？
先比較哪張更早，再移動整張記錄，親眼看數據怎樣排好。
拍完一組照片，記錄卡被打亂了。每張卡都有一個數字和一個身份字母，你想按數字從小到大整理，還不能弄丟數字相同的兩張卡。
開啟互動課程 →
先猜一下
兩個觀測記錄的排序值都是 2，排序時應該刪掉其中一個嗎？
查看答案與解釋
不應該，兩筆記錄都保留 — 數值相同不等於記錄相同；排序只改順序，不負責去重。
再把體驗和科學連結起來
先把記錄攤開
每張卡的字母是記錄身份，數字是排序依據。同一個數字可以出現多次，不能因此而丟掉記錄。
輸入是一組記錄，不是只剩互不相同的數
每次只做一個明確動作
移動進度，橘色標示比較或交換的卡片。程式在比較階段只看值，在交換階段移動完整記錄。
比較 → 決定是否交換
換個做法，結果還要一樣
原書給出逐對交換、先找最小、分區快排。不同步驟可以得到相同的升序值，但相同值的記錄未必保持原順序。
SIMPLE / BETTER / QUICKSORT
資料變多，步驟數就重要
前兩種方法的比較次數隨N²增長；快排通常約N log N，但不保證每個輸入都最快。計數是本例實測，不是機器運作秒數。
比較次數、交換次數與實際耗時要區分
把計算鏈展開
排序后：key₁ ≤ key₂ ≤ … ≤ keyₙ 排序前后：每条記錄的身份与内容保持完整
這是演算法規則課，沒有一個代入即得的天文公式。比較決定順序，交換必須移動整筆記錄；相同鍵值不表示可丟棄記錄。
試一試
用同一組卡片比較三種方法；把進度拖到100%，核對數字升序且A—H記錄仍全在。
動手看一遍 →
符號不用背
- N
- 記錄數量，本課畫面為8條
- 比較
- 查看兩個值的次序；快排也會與基準值比較
- 交換
- 把兩張完整記錄互換位置
- 基準值
- 快排用來劃分兩邊的數值
- 穩定性
- 相同排序值的記錄是否保持原先相對次序
演算法、精確度與適用範圍
原書第6章印刷頁55–58、表6.A。實作三種演算法：SIMPLE SORT依前後位置逐對比較並交換，BETTER先找剩餘最小值再交換，QUICKSORT採用中間元素值為基準的雙指標分區與明確堆疊。本課省略原BASIC依區間長短優化堆疊順序的細節，保留分區結果及實際比較/交換軌跡；不主張快排最壞情況為N log N。示範卡片數字無真實日期單位，字母僅標示身分。進度百分比會對應到該演算法的離散步驟，並顯示真實步驟編號。比較和交換分別計數，不測運轉秒數；同值記錄順序不保證穩定。章節末尾字串ASCII排序介紹在文字中說明，互動只實現數值排序。本地AA+未找到排序專用模組，結果以獨立原生數值排序與每步排列不變量核驗。
我的理解檢查
比較兩張記錄時，數據一定立刻交換嗎？
不一定 — 比較和交換是不同動作，只有演算法條件滿足時才交換。
排序後的數字一樣，就代表同值記錄的順序也一定一樣嗎？
不一定 — 是否保留同值記錄的先後關係涉及穩定性；本課三種實作不提供穩定排序保證。
原書舊電腦上測得的秒數，可以直接當成今天網頁的耗時嗎？
不可以 — 硬體、語言和實作不同；本課比較可重複的操作次數，不重複使用舊機器秒數。
排序先保證記錄完整、次序正確，再比較操作成本；數值相同的記錄不能當作重複垃圾丟掉。
Jean Meeus · Astronomical Algorithms, 2nd ed. · 第 6 章