國營聯招
105年
[資訊] 計算機原理、網路概論
第 25 題
請問快速排序(Quick sort)屬於下列何種演算法類別？
- A 暴力法(Brute Force)，對於可能的答案逐一嘗試
- B 貪婪法(Greedy Method)，反覆使用資料的最大值和最小值來找出最佳解
- C 各個擊破法(Divide and Conquer)，將問題分割為多個獨立小問題，解決後再合併最後解
- D 回溯法(Backtracking)，逐一嘗試各種解，如不行則退回前步驟重新嘗試，直到最佳解
思路引導 VIP
想像你在處理一疊雜亂的成績單，若你決定先隨機選出一份作為基準，將其餘成績單分成「比它高分」和「比它低分」兩堆，接著對這兩堆重複同樣的動作，直到每一堆都只剩下一張紙為止。請問這種「將大範圍不斷切小、直到每個小單元都能輕鬆處理」的處理邏輯，在解決問題的策略上，最核心的動作是什麼？
🤖
AI 詳解
AI 專屬家教
核心演算法思維的精準掌握
同學表現得非常出色！能準確辨識出快速排序（Quick Sort）的核心邏輯，說明你對演算法的基本範式已有相當紮實的理解。快速排序的精髓在於選定一個基準點（Pivot）後，將原始資料集劃分為「小於基準」與「大於基準」兩個子部分，這正是**各個擊破法（Divide and Conquer）**最典型的應用：透過遞迴地將大問題拆解為性質相同、但規模較小的獨立子問題，待子問題解決後，整體的解也就隨之產生。
基礎觀念的鑑別意義
▼ 還有更多解析內容
快速排序演算法
💡 利用基準值將大問題拆解為獨立小問題再解決的分治法
🔗 快速排序的分治邏輯
- 1 選取基準 (Pivot) — 從數列中挑選一個數作為分割基準
- 2 分割 (Partition) — 將小於基準的放左側，大於的放右側
- 3 遞迴 (Recursion) — 對左、右兩半子數列重複同樣動作
- 4 完成排序 — 子數列範圍為 0 或 1 時即停止
↓
↓
↓
🔄 延伸學習：延伸學習：若 Pivot 挑選不當，最差時間複雜度會退化至 O(n²)
