快速排序 (Quick Sort)
1. 原理解析
快速排序是一种基于分治思想的高效排序算法。它的核心逻辑是“先整理，再拆分”：
- 选基准（Pivot）：从数组中挑出一个元素作为基准（通常选最左边的元素）。
- 分区（Partition）：通过双指针遍历，把比基准小的数全部放到基准的左边，比基准大（或等于）的数全部放到基准的右边。这一步完成后，基准元素就落在了它最终排序后应该在的绝对位置。
- 分而治之：以基准所在的位置为分界线，对左半部分和右半部分数组重复上述过程（递归），直到每个区间只有一个元素或为空。
2. 使用场景
- 大规模数据排序：由于其优秀的平均时间复杂度O(NlogN)O(N \log N)O(NlogN)和较小的常数因子，它是工业界最常用的内部排序算法之一。
- 内存受限环境：与归并排序需要O(N)O(N)O(N)的额外数组不同，快速排序是原地排序（In-place），空间复杂度极低。
- 不要求稳定性的场景：快速排序是不稳定的排序算法（相同的元素相对位置可能会改变）。
3. 代码实战
Java 版本（双指针原地修改）
publicclassQuickSort{publicstaticvoidquickSort(int[]arr,intleft,intright){// 递归终止条件：区间内只有一个元素或没有元素if(left>=right){return;}// 1. 选取最左边的元素作为基准 (pivot)intpivot=arr[left];inti=left;intj=right;// 2. 开始分区while(i<j){// 先从右往左找，找比 pivot 小的数！(注意顺序，必须 j 先走)while(i<j&&arr[j]>=pivot){j--;}// 再从左往右找，找比 pivot 大的数！while(i<j&&arr[i]<=pivot){i++;}// 如果 i 和 j 还没相遇，说明找到了两个放错位置的元素，交换它们if(i<j){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}}// 3. 将基准元素放到中间位置// 此时 i 和 j 已经相遇，由于是 j 先走，相遇位置的值一定小于等于 pivotarr[left]=arr[i];arr[i]=pivot;// 4. 分而治之，递归处理左半部分和右半部分quickSort(arr,left,i-1);quickSort(arr,i+1,right);}}Python 版本（列表推导式直观版）
defquick_sort(arr):# 递归终止条件：数组为空或只有一个元素iflen(arr)<=1:returnarr# 选取基准（取中间元素，避免最坏情况）pivot=arr[len(arr)//2]# 分区操作（利用 Python 列表推导式）left=[xforxinarrifx<pivot]# 比基准小的放左边middle=[xforxinarrifx==pivot]# 等于基准的放中间right=[xforxinarrifx>pivot]# 比基准大的放右边# 递归拼接returnquick_sort(left)+middle+quick_sort(right)4. 核心难点 / 易错点详解
致命易错点：为什么双指针中，必须是相反方向的指针先走？
如果基准选在最左侧，必须是右指针j先走。
生活例子推演：
假设数组是[6, 1, 2, 9, 7, 3]，基准是最左边的6。
如果让左指针i先走：
i从左往右找比 6 大的，找到了9停下。- 此时轮到
j走，j从右往左找比 6 小的，结果一直走到碰到了i（因为i在9的位置）。两者相遇在元素9处！ - 循环结束，执行最后一步：将基准
6和相遇点的元素互换。 - 互换后变成
[9, 1, 2, 6, 7, 3]。
灾难发生：比基准大的9竟然被换到了基准的左边！完全破坏了分区规则。
结论（肌肉记忆口诀）：
- 左边做基准，右边先动（保证相遇点一定比基准小，换到最左边是安全的）。
- 右边做基准，左边先动（保证相遇点一定比基准大，换到最右边是安全的）。
5. 复杂度分析
- 时间复杂度：
- 平均情况：O(NlogN)O(N \log N)O(NlogN)。每次基准都能将数组大致平分为两半，递归树深度为logN\log NlogN，每层遍历NNN个元素。
- 最坏情况：O(N2)O(N^2)O(N2)。当数组已经是有序的（正序或逆序），且每次都取最边缘的元素作基准时，每次分区只能排好一个元素，递归树退化成链表。
- 空间复杂度：
- 平均情况：O(logN)O(\log N)O(logN)。原地排序不产生新数组，空间消耗来自于递归函数调用栈的深度。
- 最坏情况：O(N)O(N)O(N)。递归树退化成单链表时，调用栈深度达到NNN。