说明分治、partition 与最坏 O(n²) 的成因及优化。
思想(分治):选基准 pivot,partition 把数组分为“小于 pivot”和“大于 pivot”两部分,递归排序两段。平均 O(n log n)。
最坏 O(n²):每次 pivot 都是最值(数组已序且总选首/尾),退化成 n 次 O(n) 划分。
优化:
不稳定(相等元素可能换位);需要原地则快排,要求稳定可用归并。
题目与答案就在本页;收藏、批注和错题重练在应用内