为什么对小数据量直接插入排序要比快排更快呢？

Question

看了老师的讲解，对这块好像没有详细的解释，我的想法是，小数据量的直接插入相比快排：

1. 没有额外内存的申请和释放开销

2. 没有递归栈的开销（但对于非递归实现的呢？）

算法基础较差不知道想的对不对，希望老师能指点，非常感谢！

Answer 1

liuyubobobo 2018-07-18 13:35:27

你说的都对。

不过，更更关键的，当我们使用大O来描述算法的复杂度的时候，是忽略常数项的。大O刻画的是当数据规模无穷大的时候，算法性能的趋势。他只是一个趋势，不是精确的时间。我们说O(nlogn)的算法比O(n^2)的算法快，是因为当n无穷大的时候，哪怕O(nlogn)的算法是T = 1000000nlogn，而O(n^2)的算法是T = 2n^2，总有一个n，会使得1000000nlogn < 2n^2，并且随着n逐渐增大，这个差距越来越大（解方程，试试看这个n在哪里？）。但是，当n比较小的时候，就不一定了：）比如n=8的时候，1000000nlogn = 24000000；而2n^2只有128：）

插入排序法就是一个常数项非常小的排序算法，小于大多数排序。同时，对于有序（或者近乎有序）的数据，插入排序还可以进化成为O(n)的算法（因为第二层循环可以提前终止），而小数据量的数组，拥有更高的概率是有序的。所以，可以作为在数据量比较低的时候的一种优化手段：）

• 提问者 很厉害的jq #1

  非常感谢！

• Grant_Lian #2

  老师，为啥onlogn的常数项会比on^2大那么多？

• liuyubobobo 回复 Grant_Lian #3

  这里只是举一个相对极端例子。来说明为什么是常数项的作用，让当n小的时候，O(nlogn)的算法反而比O(n^2)的算法慢。实际上不同的nlogn的算法，常数项是不同的，通常也不会这么大，而O(n^2)的算法，也不是没有常数项：）