老师我不明白希尔排序为什么能那么快
来源：2-7 更多关于O(n^2)排序算法的思考
慕村1546111
2019-05-10
希尔排序和插入排序的唯一区别就是对比间隔的步长变长了，我不明白怎么会让他的效率提升了那么多，10w的数据插入用了7s左右，而100w数据好久，我的耐心可能不够，但是希尔确只用了1s多。
能和我说说步长的变大为什么会提升那么多吗
写回答
1回答
-
首先，插入排序的时间复杂度是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)级别这个巨大的优势：）
继续加油！：）
522019-05-10
相似问题