快速排序因其平均時間復雜度$O(n\log n)$而成為廣泛應用的高效排序算法。其核心是分治法：

1. 選擇基準 (Pivot)：從待排序序列中選取一個元素（如第一個元素$arr[0]$）。
2. 分區 (Partition)：將序列重新排列，所有小于基準的元素置于其前，大于或等于的置于其后。基準元素最終位于正確位置。
3. 遞歸排序：對基準前后的兩個子序列遞歸地應用快速排序。

關鍵特性：

• 平均高效：在平均情況下性能優異。
• 原地排序：主要操作在原始數組上進行，空間復雜度$O(\log n)$（遞歸棧）。
• 不穩定性：相等元素的相對位置可能改變。

Python實現示例：

def quick_sort(arr):"""遞歸實現快速排序"""if len(arr) <= 1:  # 基線條件：空或單元素數組已有序return arrpivot = arr[0]  # 選擇第一個元素作為基準# 創建小于基準的左子數組left = [x for x in arr[1:] if x < pivot]# 創建大于等于基準的右子數組