[面試攻略] 技術性考題:常見排序演算法

更新於 發佈於 閱讀時間約 13 分鐘

排序演算法是將一組資料(如數字陣列)按特定順序(通常是遞增或遞減)排列的過程。以下介紹五種面試常見的排序演算法,包含簡單說明、程式碼範例、時間與空間複雜度,以及面試答題技巧。所有程式碼使用Python,因為它語法簡潔,適合快速理解和白板 coding。


1. 冒泡排序(Bubble Sort)

什麼是冒泡排序?

冒泡排序就像氣泡從水底浮到水面:每次比較相鄰的兩個數字,如果順序錯了就交換它們,重複這個過程直到陣列有序。每次循環,最大的(或最小的)數字會「浮」到陣列的正確位置。

怎麼做?

  1. 從陣列開頭開始,比較每對相鄰元素(例如,arr[i] 和 arr[i+1])。
  2. 如果 arr[i] > arr[i+1](假設要遞增排序),交換它們。
  3. 重複這個過程,直到沒有需要交換的元素。

程式碼範例

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)

什麼是選擇排序?

選擇排序就像每次從一堆卡片中挑出最小的那張,放到正確位置。每次遍歷陣列,找到最小元素,然後把它放到已排序部分的末尾。

怎麼做?

  1. 將陣列分為「已排序」和「未排序」兩部分(初始時已排序部分為空)。
  2. 在未排序部分找到最小元素。
  3. 將最小元素與未排序部分的開頭交換。
  4. 重複直到所有元素都排序。

程式碼範例

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)

什麼是插入排序?

插入排序像整理撲克牌:每次從未排序部分拿一張牌,插入到已排序部分的正確位置。

怎麼做?

  1. 將陣列分為「已排序」和「未排序」兩部分(初始時第一個元素視為已排序)。
  2. 從未排序部分取第一個元素,與已排序部分的元素從後往前比較。
  3. 找到正確位置插入(移動元素以騰出空間)。
  4. 重複直到所有元素都排序。

程式碼範例

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),把陣列分成比基準小的和比基準大的兩部分,遞迴排序這兩部分。

怎麼做?

  1. 選擇一個基準(通常選第一個、最後一個或隨機元素)。
  2. 將陣列重新排列,使基準左邊的元素都比它小,右邊的都比它大(分區,partition)。
  3. 遞迴對左右兩部分排序。

程式碼範例

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)

什麼是合併排序?

合併排序也是一種「分治」演算法:將陣列分成兩半,遞迴排序每一半,然後合併兩個有序陣列。

怎麼做?

  1. 將陣列分成兩個子陣列,直到每個子陣列只有一個元素(已排序)。
  2. 合併兩個子數組合併成一個有序陣列。
  3. 重複直到整個陣列排序。

程式碼範例

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))。
  • 問題:可能問「與快速排序的區別?」(回答:合併排序穩定但需要額外空間,快速排序更快但不穩定)。

比較表

raw-image



面試應答策略

  • 理解題目:
    • 確認是否需要特定排序(例如,穩定排序)。
    • 詢問資料規模(小資料集可能用插入排序,大資料集用快速排序)。
    • 詢問是否允許額外空間(合併排序需要 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 增量)。模擬面試時,練習用簡單語言解釋,並確保程式碼乾淨無誤。祝大家面試順利!



留言
avatar-img
留言分享你的想法!
avatar-img
追極光的北極熊|軟體工程師的小天地
9會員
147內容數
歡迎來到我的部落格!這裡記錄了軟體工程師的日常生活點滴,並分享程式設計與演算法的實用教學。無論你是初學者還是有經驗的開發者,都能在這裡找到深入淺出的技術解析與實戰技巧。此外,我也會分享工作中的心路歷程與學習心得,讓你不僅學到技術,更能瞭解軟體開發的實際應用與挑戰。希望透過這個平台,能與你共同成長,激發對技術的熱情!
你可能也想看
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
高中數學主題練習—二階行列式
Thumbnail
高中數學主題練習—二階行列式
Thumbnail
高中數學主題練習—二階行列式
Thumbnail
高中數學主題練習—二階行列式
Thumbnail
※ 什麼是ORDER BY? 可以讓SELECT出來的結果,根據你想要的方式排序。簡單說,用於對查詢結果進行排序。 ※ 語法: SELECT select_list FROM table_name ORDER BY column1 [ASC|DESC], column2 [ASC|DESC]
Thumbnail
※ 什麼是ORDER BY? 可以讓SELECT出來的結果,根據你想要的方式排序。簡單說,用於對查詢結果進行排序。 ※ 語法: SELECT select_list FROM table_name ORDER BY column1 [ASC|DESC], column2 [ASC|DESC]
Thumbnail
在進行SQL查詢邏輯更改時,需要適當地使用SubQuery和join來達到新的排序需求。本文將介紹原本的撈取邏輯、需求以及如何使用SubQuery來解決新的排序需求。
Thumbnail
在進行SQL查詢邏輯更改時,需要適當地使用SubQuery和join來達到新的排序需求。本文將介紹原本的撈取邏輯、需求以及如何使用SubQuery來解決新的排序需求。
Thumbnail
題目敘述 Sort Colors 給定一個色彩陣列,裡面的顏色包含0紅色,1白色,2藍色。 要求我們透過in-place操作,把色彩陣列依序從左到右排好, 依序出現的是紅色、白色、藍色。
Thumbnail
題目敘述 Sort Colors 給定一個色彩陣列,裡面的顏色包含0紅色,1白色,2藍色。 要求我們透過in-place操作,把色彩陣列依序從左到右排好, 依序出現的是紅色、白色、藍色。
Thumbnail
計數原理的題目們,以及上次排組的解析。
Thumbnail
計數原理的題目們,以及上次排組的解析。
Thumbnail
這篇文章介紹了排列和組閤中的錯位排列和排容原理,並提供了一種相對樸實的解題方法。透過例子詳細解釋了選擇情況下的數學原理,讓讀者能夠理解並吸收。文章通過課堂上難以推敲的題目,提出了一個相對簡單的方式來解題。 圖片選自@pngtree
Thumbnail
這篇文章介紹了排列和組閤中的錯位排列和排容原理,並提供了一種相對樸實的解題方法。透過例子詳細解釋了選擇情況下的數學原理,讓讀者能夠理解並吸收。文章通過課堂上難以推敲的題目,提出了一個相對簡單的方式來解題。 圖片選自@pngtree
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News