快速排序通过分治法将数组按基准值划分为两部分并递归排序。首先选择基准（如末尾元素1），分区后小元素在左、大元素在右，如[3,6,8,10,1,2,1]变为[1,1,2,10,6,8,3]。接着对左右子数组递归执行快排，直到子数组长度为0或1。算法平均时间复杂度O(n log n)，最坏O(n²)，常用原地分区提升效率。
快速排序是一种高效的排序算法，通过“分治”的思想把一个大问题拆成小问题来解决。它的核心思路是选一个基准值（pivot），把数组分成两部分：小于基准的放左边，大于基准的放右边，然后对左右两部分递归处理。整个过程不需要额外的存储空间，属于原地排序。
选择基准与分区操作
排序开始时，从数组中选一个元素作为基准（通常选第一个、最后一个或中间元素）。然后遍历整个数组，将比基准小的元素移到左边，比基准大的移到右边。这个过程叫“分区”（partition）。
例如数组 [3, 6, 8, 10, 1, 2, 1]，如果选最后一个元素 1 为基准，经过分区后可能变成 [1, 1, 2, 10, 6, 8, 3]，此时基准 1 已经在正确位置上。
递归处理子数组
分区完成后，基准左边和右边的子数组仍然是无序的。接下来对这两个子数组分别进行同样的快速排序操作：
立即学习“Python免费学习笔记（深入）”；
- 对左半部分递归调用快排
- 对右半部分递归调用快排
递归直到子数组长度为0或1时停止，这时整个数组就有序了。
代码实现简要说明
一个简单的实现方式如下：
def quicksort(arr):if len(arr) return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
这段代码虽然清晰易懂，但使用了额外的空间。实际应用中常采用原地分区的方式（如Hoare或Lomuto分区方案）提升效率。
基本上就这些。快排平均时间复杂度是 O(n log n)，最坏情况是 O(n²)，但在合理选择基准的情况下表现非常优秀。
