面试题库 › C++ / 后端 › 数组基本有序时,用什么排序方法效率最高?

数组基本有序时,用什么排序方法效率最高?

难度 ★★☆在 3 场真实面经中被问到 方向:C++ / 后端考点:排序算法

哪些公司问过

快手1米哈游1MetaApp1

常见岗位:安卓、游戏服务端、C/C++ 软件开发

答案要点

  1. 插入排序时间为 O(n+逆序对数),基本有序时接近 O(n),稳定且常数小
  2. 冒泡加提前终止标志最好 O(n),但常数和最坏行为不如插入排序
  3. TimSort 利用已有有序段,近乎有序数据接近线性
  4. 固定选首尾基准的快排在有序输入上退化为 O(n²),可用随机或三数取中
  5. 每个元素偏离不超过 k 时,用 k+1 大小的堆可做到 O(n log k)

易错点

面试官常见追问

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

相关面试题