Quicksort
Quicksort picks a pivot, partitions values around it, then recursively sorts the partitions.
先从这个心智模型开始
Quicksort picks a pivot, partitions values around it, then recursively sorts the partitions.
它如何工作，不堆砌不必要的术语
Average time is O(n log n), but poor pivot choices can lead to O(n²).
In-place variants need little extra array memory, though recursion still uses stack space.
把算法读成一连串决策
Understand what one pass/partition/merge guarantees.
Track which region is already finalized.
Reason about comparisons, swaps/moves and extra memory.
Read a tiny input by hand and write down the state after every important operation. For Quicksort, the goal is to make the invariant visible rather than to memorize code.
function quickSort(a) {
if (a.length <= 1) return a;
const pivot = a[Math.floor(a.length / 2)];
const left = a.filter(x => x < pivot);
const equal = a.filter(x => x === pivot);
const right = a.filter(x => x > pivot);
return [...quickSort(left), ...equal, ...quickSort(right)];
}不要死记语法。跟踪每一行中发生变化的状态，并把它与上面描述的不变量联系起来。
avg O(n log n), worst O(n²)
Do not quote this complexity mechanically. Ask which operation or input dimension it describes, then derive the cost from the loops, recursion depth, data-structure operations and any preprocessing assumptions.
适用场景
- Choose based on input size, order, key range, stability and memory limits.
通常哪里会出错
- Comparing only average Big-O.
- Forgetting stability, in-place behavior, recursion depth or key-domain assumptions.
专业回答结构
Discuss pivot strategy and partition scheme. Saying only 'O(n log n)' misses the important worst-case trade-off.
What problem does Quicksort solve?
Quicksort picks a pivot, partitions values around it, then recursively sorts the partitions.
关于复杂度应该提到什么？
Its typical cost here is avg O(n log n), worst O(n²), but a complete answer should connect that cost to the representation, input constraints and the dominant operations.
最常见的错误是什么？
Comparing only average Big-O.