面试题库 › 嵌入式 › 手写快速排序及其复杂度

手写快速排序及其复杂度

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

哪些公司问过

华为2滴滴1

常见岗位:嵌入式软件、C/C++ 软件开发

答案要点

  1. 分治:选基准分区,左边不大于、右边不小于基准,再递归
  2. 分区常用双指针交换,最后把基准放到分界位置
  3. 平均时间 O(n log n),最坏 O(n²),出现在有序数组且固定取端点为基准
  4. 随机基准或三数取中可避免最坏情况
  5. 原地、不稳定,递归栈平均 O(log n);快速选择求第 k 大平均 O(n)

易错点

面试官常见追问

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

相关面试题