javascript - 有没有人知道v8在实现排序的时候为什么对小数组用插入排序？

Answer 1

你自己写个插排、快排，然后自己测量下时间不就知道了。
要么你自己写个标准的插排，再把v8里面用的那个插排弄出来，比较下代码，再测量下时间呗。

Answer 2

快排的时间平均时间复杂度是cNlog(N)，最坏情况下N^2/2,空间复杂度O(log(N))。c是一个常数,经验得出来的一个值。
插入排序平均时间复杂度N^2/4，最坏N^2/2,空间复杂度O(1)。
(上述公式也忽略了一下常数项和N的一次项，因为不是固定的)

所以 N 比较小(v8里给的是10)的时候 N^2/4不见得比 cNlog(N)大，比如设 N<=10,对数的底数取10，c=2.5的时候。
另外同样是一步运算，插入排序只需要比较，交换;而快排需要比较，交换，平均下来的一点儿空间分配。 所以 N 比较小的时候不见得插入排序是慢的。

当 N 比较大的时候上面那些常数的影响可以忽略不计，那么N^2显然是比Nlog(N)大。