algorithm - 为什么当输入规模较小时，插入排序比快速排序快？

Question

我想得到理论原因而不是实验结果。另外，我们如何确定数据大小何时称为小或大？

我没有解释清楚，我的意思是当输入数据量较小时，我们通常选择使用Insertion排序或者不使用Quick Sort，没错。所以我想知道这是为什么？

Answer 1

请记住，在渐近分析中，我们忽略常数因子。所以 Quicksort 的 O(n log n) 复杂度实际上是 O(C(n log n))，其中 C 是某个未知常数。同样，插入排序的 O(n^2) 实际上是 O(C(n^2))。我们称这些常量为 Cq 和 Ci。

所以当 (Ci * n^2) < (Cq * (n log n)) 时，插入排序会更快。

从两个算法来看，Ci < Cq 应该是显而易见的。插入排序非常简单。该算法只不过是比较和交换，并引入了一些循环开销。

快速排序稍微复杂一点，每次迭代需要更多步骤，但迭代次数更少。

考虑对一个五元素数组进行排序。插入排序会做，最坏的情况是:

• 外循环控制变量的5次递增和比较
• 内循环控制变量的15个增量和比较
• 15 个元素比较
• 15 次交换

现在看Quicksort ，在平均情况下必须划分四个子数组。 5 元素数组被分成两个包含 3 个元素和 2 个元素的子数组。 3 元素子数组进一步划分为 1 和 2 元素的子数组。然后对两个二元子数组进行划分。

所以partition方法会被调用四次。除了元素的比较和交换以及其他开销之外，每个分区步骤至少需要两次交换。当您将它们全部加起来时，您会发现 Quicksort 每次迭代做的工作更多。当迭代次数较少时，插入排序虽然迭代次数较多，但总工作量较少。

您可以逐步分析以确定“小”的理论值，其中插入排序将比快速排序更快。通常这是通过计算“基本操作”来完成的，尽管定义有些灵活。在这种情况下，它非常简单:比较、赋值或函数调用是“基本操作”。

理论结果与实验得出的结果如何匹配将取决于特定的计算机硬件以及比较的成本。如果比较的开销非常大，那么您会希望选择比较次数最少的算法。但是，如果比较成本相对较低(例如比较数字，甚至比较没有长公共(public)前缀的字符串)，那么算法开销就是限制因素，简单低效的算法胜过复杂高效的算法。