排序算法 QUICK SORT
快速排序.
选定基准值完成分区，再递归排序左右两侧。
时间平均 O(n log n) / 最坏 O(n²)额外空间平均 O(log n) / 最坏 O(n)稳定性不稳定
原理与执行逻辑
选取一个基准值，将当前区间分成较小元素、基准和其余元素三部分。基准放到最终位置后，递归处理左右区间。
执行步骤
- 取区间末尾的值为 pivot，i 指向较小元素区间的下一空位。
- 用 j 扫描基准之前的元素，遇到小于 pivot 的值就交换到 i，再增加 i。
- 扫描结束后交换 i 与末尾，使基准就位。
- 分别排序基准左侧与右侧，长度不超过 1 的区间直接返回。
关键理解
扫描时 [left, i) 中的值都小于基准，[i, j) 中的值都不小于基准。当前实现固定选末尾，分区长期偏斜时会退化为 O(n²)。
简短示例
[4, 2, 5, 3] 以 3 为基准，将 2 移到前面，再放入基准，得到 [2, 3, 5, 4]，随后处理 [5, 4]。
代码与执行动画
STEP 0 / 47function quickSort(arr, left = 0, right = arr.length - 1) { if (left >= right) return arr; const pivot = arr[right]; let i = left; for (let j = left; j < right; j++) { if (arr[j] < pivot) { [arr[i], arr[j]] = [arr[j], arr[i]]; i++; } } [arr[i], arr[right]] = [arr[right], arr[i]]; quickSort(arr, left, i - 1); quickSort(arr, i + 1, right); return arr;}高亮对应当前步骤；源码对传入数组进行原地排序。
数组状态
升序 · 8 个元素比较 0实际交换 0数组写入 0当前区间 —
待排序当前操作基准已就位
下标显示在底部；柱体随元素移动，等值元素也保留独立身份。
0
准备排序
点击下一步或自动播放，观察数组从左到右升序排列的过程。
调整待排序数组
使用相同数据切换算法，观察比较与交换过程。
快速排序的执行规则
本实现采用 Lomuto 分区，以区间末尾元素为基准；递归栈占用计入空间复杂度。
交换次数仅统计两个不同位置的交换；可输入重复值。对应题目与扩展练习
观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。
- 对应题目912. 排序数组打开题目
完整排序练习，题目要求 O(n log n)；需避免固定枢轴在有序输入下退化。