对于小案例,为什么插入排序比快速排序和冒泡排序更快？

Question

我最近读了一篇文章,讨论了算法的计算复杂性.作者提到"为什么插入排序比小型案例的快速排序和冒泡排序更快".有人可以为此做出一些解释吗？

有人知道我上面提到的每种排序算法的实际复杂性吗？

Answer 1

考虑两个复杂度函数：

F(X) = X^2
G(X) = 4 * X * ln(X)

F(3) = 9
G(3) = 13

所以算法 F 赢得了 3 项。但：

F(100) = 10,000
G(100) = 1,842

所以算法 G 赢得了 100 个项目。

插入排序的复杂度类似于F(X)。快速排序的复杂度类似于G(X)。