面试题库 › Java 后端 › 希尔排序原理与增量序列

希尔排序原理与增量序列

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

哪些公司问过

美的集团1Ucloud1

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

答案要点

  1. 希尔排序是插入排序的改进,靠增量 gap 让远距离元素大跨度移动
  2. 按 gap 分组各自插入排序,逐步缩小 gap,最后 gap=1 做一次直接插入排序
  3. 前几趟使数组基本有序,最后一趟移动很少,整体快于纯插入排序
  4. 增量序列影响复杂度:希尔增量 n/2..1,Hibbard 为 2^k-1,还有 Sedgewick 等
  5. 平均复杂度依赖增量序列,经验上约 O(n^1.3);原地排序、不稳定

易错点

面试官常见追问

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

相关面试题