本單元重點回顧

排序＝把元素按指定順序重排：花一次 O(n \log n) 的工夫，之後找最大、找第 k 名、找相同、找最接近全部變便宜。

指標是「存記憶體位置」的型態：& 取址、* 取值；int *a, b; 只有 a 是指標。位置印出來是十六進位，數值本身不重要——重要的是誰指向誰。競程幾乎不宣告指標變數，學它是為了看懂 sort(a, a + n) 與更懂函式。

陣列名稱骨子裡是指標：指向第一個元素；指標 + k 跳 k 個元素、指標相減得距離；a[i] 就是 *(a + i)——但 *p + 2 是先取值再加，跳格一定要加括號。

要讓函式改到外面的變數，有兩條路：C++ 的參考（int &a，呼叫 f(x)）與 C 的指標（int *a，呼叫 f(&x)）——後者是把門牌號碼交出去。陣列參數 int a[] 其實就是 int *a，這解釋了為什麼函式改得動陣列、為什麼長度要另外傳。

sort(開頭, 結尾下一格)：左閉右開；0-base 寫 sort(a, a + n)、1-base 寫 sort(a + 1, a + n + 1)；vector 與 string 用 begin()／end()。

由大到小用 greater()：sort(a, a + n, greater())，排什麼型態都是同一顆；舊標準要換成 greater<int>()，那時角括號裡的型態寫錯會亂排。

比較函式 cmp(x, y)＝「x 是否必須排在 y 前面」：回傳 bool；可以按絕對值、按個位數、讀全域陣列排「編號」——一份資料想怎麼排就怎麼排。

鐵則：相等必須回傳 false：用 <、> 別用 <=、>=——違反就是 UB，RE／WA／TLE 都可能，而且小測資常常抓不到。

（延伸）stable_sort＝相等元素保持原本順序：「先輸入的排前面」這種隱形次要關鍵字，交給它最省事；sort 不保證穩定。

排序後，該在一起的就在隔壁：相異計數、最接近數對、配對還原——兩兩比較的問題常塌縮成相鄰比較。

泡沫排序 O(n^2)：一輪相鄰互換讓最大值浮到最後，n - 1 輪排完；n = 10^5 就太慢，學它是為了懂原理。

計數排序 O(n + V)：把數字當索引、數出現次數再依序倒出——不比較也能排序，但值域要小、要非負（負數先平移）。

（延伸）合併兩個已排序數列只要 O(n)：雙指標「排頭比一比，小的先走」。把每個元素當成長度 1 的小段，相鄰兩段一路合併、段長 1 \to 2 \to 4 \to 8 加倍上去，就是合併排序 O(n \log n)——只用迴圈與陣列就寫得出來。