快速排序的基本思想是选择一个基准元素，通过partition函数将数组划分为两部分：一部分比基准小，另一部分比基准大，然后递归地对这两个子数组进行排序。
defquick_sort(arr):iflen(arr)<=1:returnarrelse:pivot=arr[len(arr)//2]# 选择中间元素作为基准left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)其平均时间复杂度为 $ O(n \log n) $，是同量级中性能最优的排序算法之一；最坏情况下（如数组已有序），时间复杂度退化为 $ O(n^2) $。快速排序是一种不稳定排序，相同元素的相对位置可能在排序过程中发生改变。
堆排序则是基于堆这种数据结构的排序方法。堆是一个完全二叉树的数组表示，分为大根堆和小根堆：
- 大根堆：每个父节点的值 ≥ 其子节点，堆顶为最大值；
- 小根堆：每个父节点的值 ≤ 其子节点，堆顶为最小值。
堆排序的核心步骤包括：
- 构建初始堆（以大根堆为例，将最大值置于堆顶）；
- 将堆顶元素与末尾元素交换，输出该最大值；
- 调整剩余元素使其重新满足堆的性质；
- 重复上述过程直到所有元素有序。
堆排序的时间复杂度始终为 $ O(n \log n) $，空间复杂度为 $ O(1) $，属于原地排序，但也是不稳定排序。
快速排序的原地版本通过在原数组上进行元素交换，并使用双指针技术来划分区间，避免创建额外的数组（如left,middle,right列表），从而将空间复杂度从 $ O(n) $ 优化到 $ O(\log n) $（仅用于递归调用栈）。
✅ 原地快排实现逻辑：
- 选择一个基准元素（pivot），通常选区间的第一个、最后一个或中间元素；
- 使用两个指针
i和j，在[low, high]范围内进行划分：i从左向右找大于等于 pivot 的元素；j从右向左找小于等于 pivot 的元素；- 若
i < j，则交换arr[i]和arr[j]；
- 最终将基准元素放到正确位置（与
i或j重合的位置交换）； - 递归对左右两部分排序。
🧩 Python 实现代码（原地快排）：
defquick_sort_inplace(arr,low=0,high=None):ifhighisNone:high=len(arr)-1iflow<high:# 分区操作，返回基准元素的最终位置pivot_index=partition(arr,low,high)# 递归排序基准左侧和右侧quick_sort_inplace(arr,low,pivot_index-1)quick_sort_inplace(arr,pivot_index+1,high)defpartition(arr,low,high):pivot=arr[low]# 选择第一个元素作为基准i=low+1# 左指针，从第二个元素开始j=high# 右指针，指向末尾done=Falsewhilenotdone:# 向右移动 i，直到找到大于等于 pivot 的元素whilei<=jandarr[i]<=pivot:i+=1# 向左移动 j，直到找到小于等于 pivot 的元素whilei<=jandarr[j]>=pivot:j-=1# 如果 i < j，则交换 arr[i] 和 arr[j]ifi<j:arr[i],arr[j]=arr[j],arr[i]else:done=True# 将基准元素放到正确位置arr[low],arr[j]=arr[j],arr[low]returnj# 返回基准位置# 示例使用arr=[3,6,8,10,1,2,1]quick_sort_inplace(arr)print(arr)# 输出: [1, 1, 2, 3, 6, 8, 10]⚖️ 优缺点分析：
- 优点：
- 空间复杂度仅为 $ O(\log n) $（递归深度）；
- 原地排序，节省内存；
- 实际运行速度快，缓存友好。
- 缺点：
- 不稳定排序（相同值可能改变顺序）；
- 最坏情况仍为 $ O(n^2) $（可通过随机化 pivot 改善）。
💡 提示：可进一步优化为“三路快排”或“随机选取 pivot”来应对重复元素多或有序输入的情况。
