IT 面试题库

快速排序的思想与最坏情况?

中级简答题算法工程师Java开发工程师快排分治算法

题目

说明分治、partition 与最坏 O(n²) 的成因及优化。

参考答案

内容深度:基础 · 无代码示例 · 来源:种子题库 · 未复核 · 89 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

思想(分治):选基准 pivot,partition 把数组分为“小于 pivot”和“大于 pivot”两部分,递归排序两段。平均 O(n log n)。

最坏 O(n²):每次 pivot 都是最值(数组已序且总选首/尾),退化成 n 次 O(n) 划分。

优化:

不稳定(相等元素可能换位);需要原地则快排,要求稳定可用归并。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题