Quick Sort的时间复杂度

### 快速排序算法的时间复杂度分析

#### 平均时间复杂度
快速排序的平均时间复杂度为 \(O(n\log n)\)[^1]。这一结论基于每次划分操作能够将待排序数组大致均匀分割的前提。

#### 主定理应用
对于快速排序而言，其递归关系可以表达为\(T[n] = 2T[n/2] + O(n)\)，这里\(a = 2\)、\(b = 2\)以及\(f(n)=O(n)\)。依据主定理中的条件判断，当\(f(n)\)满足一定条件下时，该类问题的时间复杂度即为\(O(n\log n)\)[^2]。

#### 最坏情况下时间复杂度
然而，在某些特殊输入序列下——比如已经有序的数据集上执行快速排序，则可能出现极不平衡的分区现象，此时递推公式变为\(T[n]=T[n−1]+T[1]+O(n)\)，最终导致整体性能退化至平方级别，也就是\(O(n^2)\)。

#### 效率提升原理
通过合理选取枢轴元素并有效实施分治策略，使得每轮迭代过程中参与比较的有效范围呈几何级数缩减而非线性减少，从而实现了更高效的排序过程[^3]。

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        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 quicksort(left)+middle+quicksort(right)

print(quicksort([3,6,8,10,1,2,1]))