概述#

理解常見的排序與搜尋演算法是面試的重要準備。許多排序和搜尋題目，其實是對這些經典演算法的變形或應用。

面對排序題時，先掃描各種演算法，看看哪一種最適合當前情境。例如：對一組年齡值排序，因為數值範圍小且資料量大，Bucket Sort 或 Radix Sort 可達到 O(n) 時間複雜度。

面試中最常考的是 Merge Sort、Quick Sort 和 Bucket Sort。

常見排序演算法#

Bubble Sort#

  • Time: O(n²) average and worst case
  • Memory: O(1)

從頭開始，比較相鄰兩個元素，若前者大於後者則交換。重複掃描直到陣列有序。較小的元素會逐漸「浮」到陣列前端。

Selection Sort#

  • Time: O(n²) average and worst case
  • Memory: O(1)

簡單但低效。每次線性掃描找到最小值，將其移到前端（與當前位置交換）。重複此過程直到全部有序。

Merge Sort#

  • Time: O(n log n) average and worst case
  • Memory: Depends（輔助空間 O(n)）

將陣列對半切分，對各半部遞迴排序，再合併兩個已排序的半部。「合併」步驟是核心所在。

void mergesort(int[] array) {
    int[] helper = new int[array.length];
    mergesort(array, helper, 0, array.length - 1);
}

void mergesort(int[] array, int[] helper, int low, int high) {
    if (low < high) {
        int middle = (low + high) / 2;
        mergesort(array, helper, low, middle);      // Sort left half
        mergesort(array, helper, middle+1, high);   // Sort right half
        merge(array, helper, low, middle, high);    // Merge them
    }
}

void merge(int[] array, int[] helper, int low, int middle, int high) {
    /* Copy both halves into a helper array */
    for (int i = low; i <= high; i++) {
        helper[i] = array[i];
    }

    int helperLeft = low;
    int helperRight = middle + 1;
    int current = low;

    /* Iterate through helper array. Compare left and right half,
     * copying back the smaller element from the two halves. */
    while (helperLeft <= middle && helperRight <= high) {
        if (helper[helperLeft] <= helper[helperRight]) {
            array[current] = helper[helperLeft];
            helperLeft++;
        } else {
            array[current] = helper[helperRight];
            helperRight++;
        }
        current++;
    }

    /* Copy the rest of the left side into the target array */
    int remaining = middle - helperLeft;
    for (int i = 0; i <= remaining; i++) {
        array[current + i] = helper[helperLeft + i];
    }
}

合併時只需複製左半部剩餘元素，因為右半部的剩餘元素已經在正確位置上。

Quick Sort#

  • Time: O(n log n) average, O(n²) worst case
  • Memory: O(log n)

隨機選取 pivot，將所有小於 pivot 的元素移到其左側，大於的移到右側。再對左右兩側遞迴排序。

當 pivot 不是中間值（例如每次都選到最大或最小值）時，會退化到 O(n²)。

void quickSort(int[] arr, int left, int right) {
    int index = partition(arr, left, right);
    if (left < index - 1) { // Sort left half
        quickSort(arr, left, index - 1);
    }
    if (index < right) { // Sort right half
        quickSort(arr, index, right);
    }
}

int partition(int[] arr, int left, int right) {
    int pivot = arr[(left + right) / 2]; // Pick pivot point
    while (left <= right) {
        // Find element on left that should be on right
        while (arr[left] < pivot) left++;
        // Find element on right that should be on left
        while (arr[right] > pivot) right--;

        // Swap elements, and move left and right indices
        if (left <= right) {
            swap(arr, left, right); // swaps elements
            left++;
            right--;
        }
    }
    return left;
}

Radix Sort#

  • Time: O(kn)（其中 k 為排序演算法的趟數）

Radix Sort 專用於整數（及部分其他資料類型），利用整數具有固定位數的特性。

從最低位（或最高位）開始，依每一個數位進行分組排序，重複直到整個陣列排序完成。

不同於比較排序演算法（最好也要 O(n log n)），Radix Sort 的時間複雜度為 O(kn)，其中 n 是元素數量，k 是排序趟數。

搜尋演算法#

Binary Search（二元搜尋）#

在有序陣列中搜尋元素 x，步驟如下：

  1. 比較 x 與陣列中間點
  2. 若 x 小於中間點，搜尋左半部
  3. 若 x 大於中間點，搜尋右半部
  4. 重複直到找到 x 或子陣列為空

二元搜尋的實作細節（±1 的邊界處理）比想像中容易出錯，務必仔細確認。

int binarySearch(int[] a, int x) {
    int low = 0;
    int high = a.length - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;
        if (a[mid] < x) {
            low = mid + 1;
        } else if (a[mid] > x) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return -1; // Error
}

int binarySearchRecursive(int[] a, int x, int low, int high) {
    if (low > high) return -1; // Error

    int mid = (low + high) / 2;
    if (a[mid] < x) {
        return binarySearchRecursive(a, x, mid + 1, high);
    } else if (a[mid] > x) {
        return binarySearchRecursive(a, x, low, mid - 1);
    } else {
        return mid;
    }
}

搜尋的延伸思考#

搜尋資料結構不只有二元搜尋一種方式。依照資料結構的不同，可以考慮：

  • 利用 Binary Search Tree 搜尋節點
  • 使用 Hash Table 進行 O(1) 查找

不要將搜尋思維侷限於二元搜尋。根據資料結構的特性，選擇最合適的搜尋方式。

面試題目列表#

題號題目
10.1Sorted Merge：合併兩個已排序的陣列 A 和 B（A 有足夠緩衝空間）
10.2Group Anagrams：將字串陣列排序，使所有 anagram 相鄰
10.3Search in Rotated Array：在旋轉過的已排序陣列中搜尋元素
10.4Sorted Search, No Size：在無法取得大小的陣列結構中搜尋
10.5Sparse Search：在包含空字串的已排序字串陣列中搜尋
10.6Sort Big File：排序一個 20 GB 的文字檔
10.7Missing Int：在 40 億個非負整數中找出一個不存在的整數
10.8Find Duplicates：在只有 4 KB 記憶體的條件下找出重複元素
10.9Sorted Matrix Search：在每行每列均已排序的矩陣中搜尋元素
10.10Rank from Stream：從整數串流中查詢某數的 rank
10.11Peaks and Valleys：將整數陣列排列為峰谷交替序列
Backward System Design and Scalability Testing Forward