老师我不明白希尔排序为什么能那么快

Question

希尔排序和插入排序的唯一区别就是对比间隔的步长变长了，我不明白怎么会让他的效率提升了那么多，10w的数据插入用了7s左右，而100w数据好久，我的耐心可能不够，但是希尔确只用了1s多。
能和我说说步长的变大为什么会提升那么多吗

Answer 1

liuyubobobo 2019-05-10 14:31:06

首先，插入排序的时间复杂度是O(n^2)的；

希尔排序的时间复杂度分析非常复杂，已经远远超过这个课程，甚至超出了大多数本科乃至研究生计算机专业的数学要求了。整体而言，希尔排序的复杂度，介乎于插入排序，选择排序这种O(n^2)复杂度的排序算法和归并排序，快速排序这种O（nlogn）级别的排序算法之间。你可以简单理解成希尔排序是一个O(n^1.5)这个复杂度的算法。

是的，O(n^2)和O(n^1.5)之间的差距就是这么大。

假设n=100w。

这意味n^2 = 10^12；而n^15=10^9。他们之间相差1000倍。

当然，这个计算不严格，因为大O不看常数项和系数，但足以说明，当n很大的时候，复杂度分析的意义。这本身也是我们学习算法的意义：）

至于希尔排序是怎么做到这么快的？其实就是在每一轮，都逐渐在让数组有序，从而使得运用插入排序算法的时候，越来越近接插入排序的最优情况。他在尽最大可能发挥插入排序在完全有序的情况下，算法会进化成为O(n)级别这个巨大的优势：）

继续加油！：）

• 提问者 慕村1546111 #1

  非常感谢！

• 提问者 慕村1546111 #2

  我似乎明白了，加大步长的用意了，他居然比语言(js)自带的排序还快了三倍，这真的不可思议。唯一的不足可能不是稳定排序吧。谢谢老师