希尔排序原理与增量序列
哪些公司问过
美的集团1Ucloud1
答案要点
- 希尔排序是插入排序的改进,靠增量 gap 让远距离元素大跨度移动
- 按 gap 分组各自插入排序,逐步缩小 gap,最后 gap=1 做一次直接插入排序
- 前几趟使数组基本有序,最后一趟移动很少,整体快于纯插入排序
- 增量序列影响复杂度:希尔增量 n/2..1,Hibbard 为 2^k-1,还有 Sedgewick 等
- 平均复杂度依赖增量序列,经验上约 O(n^1.3);原地排序、不稳定
易错点
- 以为希尔排序稳定,实际跨距离交换使它不稳定
- 随意选增量序列,坏的增量会让复杂度退化
- 忘记最后 gap 必须缩到 1,否则不能保证完全有序
- 把希尔排序的复杂度简单记成 O(n log n),它依赖增量序列
面试官常见追问
- 希尔排序为什么比直接插入排序快?
- 希尔排序为什么是不稳定的?
- 增量序列怎么影响性能?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场