插入排序为什么在处理小规模数据时比快速排序和冒泡排序更快？

Question

我最近读到一篇关于算法计算复杂度的文章。作者提到了“为什么插入排序对于小规模情况比快速排序和冒泡排序更快”。有人能解释一下吗？

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

- antonio081014

---

它是说“小规模案例”还是类似于“几乎排序好的案例”或者“少量差异”的吗？对于小规模案例，修改后的冒泡排序比插入排序更快。 - Foo Bah

@FooBah，我说的是小规模的案例，也就是指规模较小的案例。 - antonio081014

那么你所读的是错误的。对于小规模的情况，冒泡排序比插入排序更快。 - Foo Bah

@FooBah，你的结论是否还有进一步的数学支持？我指的是任何数学表达式或公式，请... - antonio081014

Answer 1

考虑两个复杂度函数:

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

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

因此，对于3项，算法F胜出。但是：

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

所以，对于100项，算法G胜出。

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

- David Schwartz

---

Naïve QuickSort 的最坏情况复杂度为 O(N^2)；正常情况下的复杂度为 O(N log N)。插入排序和冒泡排序的复杂度均为 O(N^2)。 - Jonathan Leffler

不解释插入排序如何胜过冒泡排序。 - Foo Bah

根据Sedgewick的说法，平均冒泡排序使用N^2 / 2次比较和N^2 / 2次交换。插入排序使用N^2 / 4次比较和N^2 / 8次交换。两者都是O(N^2)的时间复杂度，但其他因素使得插入排序更快。 - rossum

@rossum 我不反对针对大 N 的分析。但对于小 N，开销和其他因素实际上支持冒泡排序。 - Foo Bah

Answer 2

如果列表已经排序，快速排序需要通过所有递归步骤才能得到大小为1的n个列表。这两者都需要时间。但插入排序将遍历整个列表一次并找出它已完成。这是这种情况下最快的方法。

当列表很小时，进行递归调用和查找枢轴值等的开销比插入排序中使用的迭代过程要慢得多。

- jamesatha

---

冒泡排序对于已排序的列表只需要1次遍历。当列表被排序时，你可以停止排序。 - Foo Bah

Foo Bah，好的调用。我之前考虑了错误的排序方式，并已编辑过它。 - jamesatha

Answer 3

每种排序算法的实际复杂度如下：

1. 最佳情况 - 插入排序：O(N ^ 2), O(N), O(N ^ 2)
2. 平均情况 - 快速排序：O(N ^ 2), O(N log N), O(N log N)
3. 最差情况 - 冒泡排序：O(N ^ 2), O(N), O(N ^ 2)

- Sitesh Shrivastava

---

你知道每个平均情况的实际数学表达式吗？ - antonio081014

对于快速排序，时间复杂度为T(n) = O(n) + 2T(n/2)如果您有Cormen的书，其中对这些算法进行了详尽的分析。 - Sitesh Shrivastava

@SITZ，全世界都称之为CLR或CLRS。 - Foo Bah