【什么叫快速排序】快速排序（Quick Sort）是一種高效的排序算法，由英國計算機科學家托尼·霍爾（Tony Hoare）于1960年提出。它采用“分治法”（Divide and Conquer）的策略，通過不斷將數據分成較小的子集，并對每個子集進行遞歸排序，最終實現整個數據集的有序排列。
快速排序的核心思想是選擇一個基準值（pivot），然后將數組中比基準值小的元素放在其左側，比基準值大的元素放在其右側。這個過程稱為“分區”（partition）。之后，對左右兩個子數組重復上述過程，直到所有子數組都只有一個元素或為空為止。
一、快速排序的基本步驟
| 步驟 | 操作說明 |
| 1 | 選擇一個基準值（通常選第一個、最后一個或中間的元素） |
| 2 | 將數組中比基準值小的元素移到左邊，大的移到右邊 |
| 3 | 對左右兩個子數組遞歸執行相同操作 |
| 4 | 當子數組長度為1或0時，排序完成 |
二、快速排序的特點
| 特點 | 說明 |
| 時間復雜度 | 平均 O(n log n)，最壞 O(n2) |
| 空間復雜度 | O(log n)（遞歸棧空間） |
| 穩定性 | 不穩定（相同元素順序可能改變） |
| 是否需要額外空間 | 需要，但為原地排序（in-place） |
| 適用場景 | 數據量較大、不需要穩定排序的場合 |
三、快速排序的優缺點
| 優點 | 缺點 |
| 排序速度快，效率高 | 最壞情況下性能較差 |
| 原地排序，空間消耗少 | 不適合小數據集（不如插入排序快） |
| 實現相對簡單 | 對基準值的選擇敏感，容易影響性能 |
四、示例（以數組 [5, 3, 8, 4, 2] 為例）
1. 選擇基準值（如選第一個元素 5）
2. 分區后得到：[3, 2, 4], [5], [8
3. 對左半部分 [3, 2, 4] 繼續排序
4. 選擇基準值 3，分區后得 [2], [3], [4
5. 左右子數組均為單元素，排序結束
6. 最終結果：[2, 3, 4, 5, 8
五、快速排序的應用
- 數據庫索引排序
- 快速查找最小/最大值
- 在編程語言標準庫中廣泛使用（如 Python 的 `sorted()` 函數內部實現）
總結
快速排序是一種基于分治策略的高效排序算法，適用于大多數通用排序場景。雖然其最壞情況性能不佳，但在實際應用中，通過合理選擇基準值（如隨機化或三數取中法），可以有效避免最壞情況，提升整體效率。
