單元地圖

¶前置知識

• ✓ 陣列的宣告、遍歷與計數陣列（上冊 6.1、6.4、6.7）
• ✓ 函式的定義與內建函式 swap（上冊 7.1、7.6）
• ✓ 傳值與傳參考的差別（上冊 7.5）
• ✓ 把陣列當作函式參數、陣列名稱的意義（上冊 7.7）
• ✓ vector 與 iterator（下冊 10.2、10.5）
• ✓ pair 與它的比較規則（下冊 10.11）
• ✓ 字典序的定義（下冊 8.9）

¶學習成果

本單元結束後，你將能夠：

• ✓ 說出排序的定義，並舉例說明資料排好之後哪些處理會變簡單
• ✓ 看懂指標的宣告與 &、* 兩個運算子，說出 sort(a, a + n) 兩個參數的意義
• ✓ 分辨 *(p + 2) 與 *p + 2，說出指標與 iterator 的差別
• ✓ 看懂用指標當函式參數的寫法，並解釋函式為什麼改得動傳進去的陣列
• ✓ 用指標寫出「交換、算距離、加總、反轉」四種基本操作（11.2、11.3 各附兩題函式實作題）
• ✓ 用內建 sort 排序陣列、vector 與 string，並用 greater() 改成由大到小
• ✓ 寫出自定義比較函式，實現各種排序規則（含讀全域陣列的「編號排序」）
• ✓ 說出比較函式的鐵則——相等必須回傳 false——以及違反它的悲慘下場
• ✓ （延伸）說出 stable_sort 與 sort 的差別，判斷什麼時候需要穩定排序
• ✓ 用「排序後相鄰」的思維解掉相異計數、最接近數對、配對還原等經典問題
• ✓ 白話說明泡沫排序與計數排序的原理、寫出完整程式，並估計它們的運算量
• ✓ （延伸）寫出「合併兩個已排序數列」的程式，並用它從頭排好整個數列（簡化版合併排序）