来学习

# 快速排序算法笔记 ## 算法思想 **快速排序**是分治思想的典型应用，通过选取基准元素将数组分成两部分，递归排序后合并。 ### 核心步骤 1. 选择基准（通常取首个或末尾元素） 2. 划分：小于基准放左侧，大于放右侧 3. 递归对左右子数组排序 ## 时间复杂度分析 - **最好/平均**：O(n log n) - **最坏**：O(n²)，如数组已有序 期望复杂度推导： \[ T(n) = 2T(n/2) + n = O(n \log n) \] ## 代码实现 ``` def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quick_sort(left) + middle + quick_sort(right) ```