排序演算法是將一組資料（如數字陣列）按特定順序（通常是遞增或遞減）排列的過程。以下介紹五種面試常見的排序演算法，包含簡單說明、程式碼範例、時間與空間複雜度，以及面試答題技巧。所有程式碼使用Python，因為它語法簡潔，適合快速理解和白板 coding。
1. 冒泡排序（Bubble Sort）
什麼是冒泡排序？
冒泡排序就像氣泡從水底浮到水面：每次比較相鄰的兩個數字，如果順序錯了就交換它們，重複這個過程直到陣列有序。每次循環，最大的（或最小的）數字會「浮」到陣列的正確位置。
怎麼做？
- 從陣列開頭開始，比較每對相鄰元素（例如，arr[i] 和 arr[i+1]）。
- 如果 arr[i] > arr[i+1]（假設要遞增排序），交換它們。
- 重複這個過程，直到沒有需要交換的元素。
程式碼範例
def bubble_sort(arr):
n = len(arr)
for i in range(n): # 外層循環：控制遍歷次數
for j in range(0, n - i - 1): # 內層循環：比較相鄰元素
if arr[j] > arr[j + 1]: # 如果順序錯誤，交換
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# 測試
arr = [64, 34, 25, 12, 22]
print(bubble_sort(arr)) # 輸出: [12, 22, 25, 34, 64]
複雜度
- 時間複雜度： 最好：O(n)（陣列已排序，幾乎無交換）。 平均/最壞：O(n^2)（每次都要比較和交換）。
- 空間複雜度：O(1)（原地排序，只用幾個變數）。
- 穩定性：穩定（相同元素的相對順序不變）。
適用場景
- 適合教學或非常小的資料集（例如，n < 50）。
- 實務中幾乎不用，因為效率低。
面試Tips
- 講解時：用「氣泡浮起來」的比喻，讓面試官覺得你能把複雜概念講得簡單。
- 優化：提到可以加一個旗標（flag）檢查是否已排序，若無交換則提前結束。
- 問題：面試官可能問「如何優化？」或「為什麼不用在實務中？」（回答：效率低，快速排序或內建排序更好）。
2. 選擇排序（Selection Sort）
什麼是選擇排序？
選擇排序就像每次從一堆卡片中挑出最小的那張，放到正確位置。每次遍歷陣列，找到最小元素，然後把它放到已排序部分的末尾。怎麼做？
- 將陣列分為「已排序」和「未排序」兩部分（初始時已排序部分為空）。
- 在未排序部分找到最小元素。
- 將最小元素與未排序部分的開頭交換。
- 重複直到所有元素都排序。
程式碼範例
def selection_sort(arr):
n = len(arr)
for i in range(n): # 外層循環：遍歷每個位置
min_idx = i # 假設當前位置是最小值
for j in range(i + 1, n): # 內層循環：找未排序部分的最小值
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i] # 交換
return arr
# 測試
arr = [64, 34, 25, 12, 22]
print(selection_sort(arr)) # 輸出: [12, 22, 25, 34, 64]
複雜度
- 時間複雜度： 最好/平均/最壞：O(n^2)（每次都要遍歷未排序部分）。
- 空間複雜度：O(1)（原地排序）。
- 穩定性：不穩定（交換可能改變相同元素的相對順序）。
適用場景
- 適合小資料集或當交換成本高時（因為交換次數比冒泡排序少）。
- 實務中很少使用。
面試Tips
- 講解時：用「挑卡片」的比喻，強調每次選最小值的邏輯。
- 問題：可能問「與冒泡排序的區別？」（回答：選擇排序交換次數少，但比較次數相同）。
- 陷阱：注意穩定性問題，解釋為什麼不穩定（例如，[5a, 5b, 3] 可能變成 [3, 5b, 5a]）。
3. 插入排序（Insertion Sort）
什麼是插入排序？
插入排序像整理撲克牌：每次從未排序部分拿一張牌，插入到已排序部分的正確位置。
怎麼做？
- 將陣列分為「已排序」和「未排序」兩部分（初始時第一個元素視為已排序）。
- 從未排序部分取第一個元素，與已排序部分的元素從後往前比較。
- 找到正確位置插入（移動元素以騰出空間）。
- 重複直到所有元素都排序。
程式碼範例
def insertion_sort(arr):
n = len(arr)
for i in range(1, n): # 從第二個元素開始
key = arr[i] # 當前要插入的元素
j = i - 1 # 已排序部分的末尾
while j >= 0 and arr[j] > key: # 比較並移動
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key # 插入
return arr
# 測試
arr = [64, 34, 25, 12, 22]
print(insertion_sort(arr)) # 輸出: [12, 22, 25, 34, 64]
複雜度
- 時間複雜度： 最好：O(n)（陣列幾乎已排序，僅需少量移動）。 平均/最壞：O(n^2)（需要多次比較和移動）。
- 空間複雜度：O(1)（原地排序）。
- 穩定性：穩定。
適用場景
- 適合小資料集或部分已排序的資料（例如，線上資料流）。
- 在某些情況下比冒泡排序快（移動比交換快）。
面試Tips
- 講解時：用「撲克牌」的比喻，強調逐步構建已排序部分的過程。
- 優勢：提到插入排序在「幾乎排序」的情況下效率高。
- 問題：可能問「如何應用於實際場景？」（回答：適合小規模或增量排序，如資料即時插入）。
4. 快速排序（Quick Sort）
什麼是快速排序？
快速排序是一種高效的「分治」演算法：選一個基準（pivot），把陣列分成比基準小的和比基準大的兩部分，遞迴排序這兩部分。
怎麼做？
- 選擇一個基準（通常選第一個、最後一個或隨機元素）。
- 將陣列重新排列，使基準左邊的元素都比它小，右邊的都比它大（分區，partition）。
- 遞迴對左右兩部分排序。
程式碼範例
def quick_sort(arr, low, high):
if low < high:
# 找到基準的位置
pi = partition(arr, low, high)
# 遞迴排序左右部分
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
return arr
def partition(arr, low, high):
pivot = arr[high] # 選擇最後一個元素作為基準
i = low - 1 # 小於基準的區域邊界
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i] # 交換
arr[i + 1], arr[high] = arr[high], arr[i + 1] # 放置基準
return i + 1 # 返回基準位置
# 測試
arr = [64, 34, 25, 12, 22]
quick_sort(arr, 0, len(arr) - 1)
print(arr) # 輸出: [12, 22, 25, 34, 64]
複雜度
- 時間複雜度： 最好/平均：O(n log n)（分區均衡）。 最壞：O(n^2)（陣列已排序且選第一個/最後一個作為基準）。
- 空間複雜度：O(log n)（遞迴棧，平均情況）。
- 穩定性：不穩定。
適用場景
- 適合大多數通用排序場景，特別是大資料集。
- 是許多內建排序函數（如Python的 sorted）的基礎。
面試Tips
- 講解時：畫圖展示分區過程，強調「分治」的概念。
- 優化：提到選擇基準的策略（隨機基準、中間值）可避免最壞情況。
- 問題：可能問「如何處理最壞情況？」（回答：隨機化基準或使用三數取中）。
5. 合併排序（Merge Sort）
什麼是合併排序？
合併排序也是一種「分治」演算法：將陣列分成兩半，遞迴排序每一半，然後合併兩個有序陣列。
怎麼做？
- 將陣列分成兩個子陣列，直到每個子陣列只有一個元素（已排序）。
- 合併兩個子數組合併成一個有序陣列。
- 重複直到整個陣列排序。
程式碼範例
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
# 遞迴排序左右部分
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# 合併
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:]) # 加入剩餘元素
result.extend(right[j:])
return result
# 測試
arr = [64, 34, 25, 12, 22]
print(merge_sort(arr)) # 輸出: [12, 22, 25, 34, 64]
複雜度
- 時間複雜度： 最好/平均/最壞：O(n log n)（總是均分陣列）。
- 空間複雜度：O(n)（需要額外空間合併）。
- 穩定性：穩定。
適用場景
- 適合需要穩定排序或鏈表排序（因為合併鏈表效率高）。
- 適合大資料集，但記憶體使用較多。
面試Tips
- 講解時：畫圖展示分分合合的過程，強調穩定性。
- 優勢：提到合併排序在鏈表上的應用（空間複雜度可降為 O(1)）。
- 問題：可能問「與快速排序的區別？」（回答：合併排序穩定但需要額外空間，快速排序更快但不穩定）。
比較表
面試應答策略
- 理解題目：
- 確認是否需要特定排序（例如，穩定排序）。
- 詢問資料規模（小資料集可能用插入排序，大資料集用快速排序）。
- 詢問是否允許額外空間（合併排序需要 O(n) 空間）。
- 講解思路：
- 用簡單的比喻（氣泡、撲克牌、分治）讓面試官明白你的思考。
- 畫圖展示過程（例如，快速排序的分區或合併排序的合併）。
- 提到時間和空間複雜度，解釋為什麼選擇某種排序。
- 程式碼實現：
- 寫乾淨的程式碼，使用有意義的變數名（pivot, min_idx）。
- 註釋關鍵步驟，特別是迴圈或遞迴。
- 處理邊界情況（空陣列、單元素陣列）。
- 優化與討論：
- 如果時間複雜度高（如 O(n^2)），提到更高效的替代方案（快速排序、合併排序）。
- 討論穩定性（例如，合併排序適合需要穩定的場景）。
- 提到實務中的選擇：大多數語言的內建排序（如Python的 sorted）是快速排序和插入排序的混合。
- 常見追問：
- 「為什麼不用內建排序？」回答：內建排序（如Python的Timsort）已優化，但在面試中需要理解底層原理。
- 「如何處理大資料？」回答：快速排序或合併排序，考慮外部排序（分塊讀入記憶體）。
- 「穩定性重要嗎？」回答：如果需要保持相同元素的相對順序（例如，按多欄排序），穩定性很重要。
- 模擬面試準備：
- 在LeetCode練習排序相關題目（例如，#912 Sort an Array）。
- 手寫程式碼，模擬白板環境，練習邊寫邊講解。
- 準備2-3個排序演算法的程式碼，確保能快速寫出（推薦快速排序和插入排序）。
其他排序演算法（簡單提及）
面試中可能提到但不常要求手寫的排序：
- 堆排序（Heap Sort）：
- 時間：O(n log n)，空間：O(1)，不穩定。
- 基於堆資料結構，適合需要固定記憶體的場景。
- 計數排序（Counting Sort）：
- 時間：O(n + k)（k 是範圍大小），空間：O(k)，穩定。
- 適合範圍小的整數排序（例如，0到100）。
- 基數排序（Radix Sort）：
- 時間：O(d * (n + k))（d 是數字位數），空間：O(n + k)，穩定。
- 適合多位數或字串排序。
如果面試官提到這些，簡單說明原理和適用場景即可，除非要求詳細實現。
結語
排序演算法是面試的必考點，理解每種排序的原理、複雜度和適用場景能讓你脫穎而出。練習時，專注於快速排序和插入排序，因為它們在面試中出現頻率高且代表不同類型（分治 vs 增量）。模擬面試時，練習用簡單語言解釋，並確保程式碼乾淨無誤。祝大家面試順利！
