希尔排序平均时间复杂度

Question

你某鸟有人维护也是懂眼瞎的

---

你百度文库也是懂胡说八道的

---

也是逆天的，写这么多字说了依托勾石

---

评论里“可读性很强”的某N文章

---

• <input disabled="" type="checkbox" /> 希望收到希尔排序平均时间复杂度的通俗证明，我想看懂
• <input disabled="" type="checkbox" /> 希望收到希尔排序平均时间复杂度的通俗证明，我想看懂
• <input disabled="" type="checkbox" /> 用数字解释下插入到希尔优化的点，我目前知道是减少多余移位次数导致的，但是减少了什么数量级不知道
• <input disabled="" type="checkbox" /> Hibbard增量的希尔排序最坏运行时间$O(n^{\frac{3}{2}})$ 的定性原因

吐槽：你某N别看同行拉胯跟着摆，悬赏纯为了支持大家而不是你希望你有自知之明。提问的编辑器就已经够垃圾的了，还不如学习通

Answer 1

微信GPT协助作答
我来帮你把关

希尔排序（Shell Sort）是一种插入排序的改进版本，通过比较相距一定间隔的元素进行插入排序，然后逐步缩小这个间隔，最终实现整体的插入排序。希尔排序的时间复杂度并不容易精确计算，因为它与所选择的间隔序列有关。

在最坏情况下，希尔排序的时间复杂度为O(n^2)；在最好情况下，时间复杂度为O(n log^2 n)；而在平均情况下，其时间复杂度通常被认为是介于O(n log n)和O(n^2)之间。因为希尔排序的时间复杂度取决于间隔序列的选择，所以具体的平均时间复杂度会根据不同的实现及间隔序列而变化。