Lab 導讀：遞迴與排序

Week 6 的 Lab 回頭鞏固兩個 Week 4–5 的核心技巧：遞迴與排序。 它們在本週的位置並不突兀——第 [sec:adt] 節的鏈結串列天生適合遞迴處理， 第 [sec:generics] 節的 與 都建立在排序之上， 而「把演算法當參數傳」正是介面的又一個應用。 隨附程式在 底下的 資料夾。

遞迴：兩個部分，一個信念

/** n! = n × (n-1)!，0! = 1。前置條件：n >= 0 */
static long factorial(int n) {
    if (n == 0) return 1;                // 基底情況
    return n * factorial(n - 1);         // 遞迴情況：n 嚴格變小
}

/** 陣列 arr[from..] 的總和：第一個元素 + 其餘元素的總和。 */
static int sum(int[] arr, int from) {
    if (from >= arr.length) return 0;    // 基底：沒有元素了
    return arr[from] + sum(arr, from + 1);
}

/** 迴文判斷：頭尾相同，且中間也是迴文。 */
static boolean isPalindrome(String s) {
    if (s.length() <= 1) return true;
    if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
    return isPalindrome(s.substring(1, s.length() - 1));
}

輔助參數與對外包裝

很多遞迴需要「多出來的參數」記錄進度（ 的 、二分搜尋的 ／）。 呼叫者不該知道這些細節，所以慣例是寫一個對外的簡潔版本包住它——這和封裝的精神一致：

static int binarySearch(int[] haystack, int needle, int lo, int hi) {
    if (lo > hi) return -1;                          // 基底：範圍變空，確定不存在
    int mid = (lo + hi) / 2;
    if (haystack[mid] == needle)      return mid;
    else if (haystack[mid] < needle)  return binarySearch(haystack, needle, mid + 1, hi);  // 右半
    else                              return binarySearch(haystack, needle, lo, mid - 1);  // 左半
}

/** 對外版本：呼叫者不需要知道 lo/hi。 */
static int binarySearch(int[] haystack, int needle) {
    return binarySearch(haystack, needle, 0, haystack.length - 1);
}

二分搜尋每一層把範圍減半，所以只需 \(\bigO{\log n}\) 層——這是的典型： 分（切成更小的子問題）、治（遞迴解決）、合（組合答案）。 快速冪 也是：算一次 再平方，\(2^{1000}\) 只需約 10 層。

排序：兩條後置條件

四種演算法的核心想法與迴圈不變量（每回合開始時都成立的事）：

static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        // INV: arr[0..i-1] 已排序
        int x = arr[i];
        int j = i - 1;
        while (j >= 0 && less(x, arr[j])) {
            arr[j + 1] = arr[j];             // 比 x 大的元素往右挪一格
            j = j - 1;
        }
        arr[j + 1] = x;                      // 放進空出來的位置
    }
}

static int[] mergeSort(int[] input, int start, int end) {
    if (end < start)  return new int[]{};              // 基底：空範圍
    if (end == start) return new int[]{input[start]};  // 基底：單一元素本身就是排好的
    int mid = (start + end) / 2;                       // 分
    int[] left  = mergeSort(input, start, mid);        // 治
    int[] right = mergeSort(input, mid + 1, end);
    return merge(left, right);                         // 合：O(left + right)
}

實測：比較次數

把每次 比較都記錄下來，對 \(n = 2000\) 的三種資料實測（）：

• 選擇排序完全不看資料：不管輸入如何都是 \(\binom{n}{2} = 1{,}999{,}000\) 次。

• 氣泡與插入排序對「幾乎排好」的資料很快（\(n-1 = 1999\) 次），這是它們在小型或近乎有序資料上仍被使用的原因。

• 合併排序約 \(n \log_2 n \approx 2000 \times 11 = 22{,}000\) 的量級，比 \(n^2\) 少了一百倍；\(n\) 越大差距越誇張。 代價是需要 \(\bigO{n}\) 的額外空間。Java 的 對物件用的是合併排序的改良版（TimSort）。

• ：相等的元素排序後保持原本的相對順序。 中「相等取左邊」就是為了穩定。 當你先依名字排序、再依年級排序，穩定排序能保證同年級的人仍按名字排列。

把演算法當參數： 介面

測試程式如何對四種排序跑同一組測試？定義一個只有一個方法的介面，再把方法參照（method reference）當成它的實作傳進去：

interface Sorter { void sort(int[] arr); }          // 函式介面：只有一個抽象方法

static void checkSorter(String name, Sorter sorter) {
    for (int[] original : cases) {
        int[] toSort = original.clone(), expected = original.clone();
        Arrays.sort(expected);
        sorter.sort(toSort);                         // 呼叫「被傳進來的演算法」
        assert Arrays.equals(toSort, expected) : name + " 失敗：" + Arrays.toString(toSort);
    }
}
checkSorter("insertionSort", Sorting::insertionSort);   // Sorting::insertionSort 自動變成一個 Sorter
checkSorter("mergeSort", Sorting::mergeSort);

這是第 [sec:adt] 節「介面 = 契約」的另一種用法：契約只有一條「給你一個陣列，把它排好」，任何滿足契約的函式都能插進來。 第 [sec:generics] 節的 與第 [sec:ws7] 節的 都是同一個模式。

Lab 練習