排序演算法是將一組資料(如數字陣列)按特定順序(通常是遞增或遞減)排列的過程。以下介紹五種面試常見的排序演算法,包含簡單說明、程式碼範例、時間與空間複雜度,以及面試答題技巧。所有程式碼使用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 增量)。模擬面試時,練習用簡單語言解釋,並確保程式碼乾淨無誤。祝大家面試順利!