快速排序的核心思想与实现？最坏情况是什么？
思想：分治法。选「基准 pivot」，把小于基准的放左、大于的放右，再递归处理左右两半。
function quickSort(arr, lo = 0, hi = arr.length - 1) {
if (lo >= hi) return arr
const pivot = arr[hi]
let i = lo
for (let j = lo; j < hi; j++) {
if (arr[j] < pivot) { [arr[i], arr[j]] = [arr[j], arr[i]]; i++ }
}
[arr[i], arr[hi]] = [arr[hi], arr[i]] // pivot 归位
quickSort(arr, lo, i - 1)
quickSort(arr, i + 1, hi)
return arr
}- 平均
O(n log n)，最坏（已排序 + 取末位 pivot）O(n^2) - 优化：随机选 pivot / 三数取中，避免最坏
- 原地、常数空间
O(log n)（递归栈）；不稳定