面试题库 › C++ / 后端 › O(n) 的排序算法(计数、基数、桶排序)

O(n) 的排序算法(计数、基数、桶排序)

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

哪些公司问过

虎牙1钉钉1

常见岗位:C++ 后端、C/C++ 软件开发

答案要点

  1. 比较排序下限是 O(n log n),线性排序依赖数据本身的特性
  2. 计数排序 O(n+k),适合值域 k 较小的整数
  3. 桶排序在数据均匀分布时平均 O(n),分布不均会退化
  4. 基数排序 O(d(n+b)),每趟必须稳定,int32 可按 8 位分 4 趟
  5. 负数可翻转符号位或加偏移转成无符号数后再做基数排序

易错点

面试官常见追问

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

相关面试题