面试题库 › 嵌入式 › 快排分区函数、最坏复杂度与非递归实现

快排分区函数、最坏复杂度与非递归实现

难度 ★★☆在 1 场真实面经中被问到 方向:嵌入式考点:排序算法

哪些公司问过

大疆1

常见岗位:嵌入式软件

答案要点

  1. 分区:选基准,双指针交替从两端找不满足条件的元素填坑,返回基准最终位置
  2. 最坏 O(n²),出现在已有序且取端点为基准等极不平衡划分
  3. 随机基准、三数取中缓解最坏情况,重复元素多时用三路划分
  4. 非递归:显式栈保存区间边界,循环弹出分区再压入子区间
  5. 先处理较小区间,栈深度可控制在 O(log n)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题