当输入规模较小时，为什么插入排序比快速排序更快？
当输入大小较小时，插入排序比快速排序快的原因是：
- 在渐近分析中，我们忽略常数因子。因此，快速排序的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次交换
- 现在来看快速排序，平均情况下需要对四个子数组进行划分。五个元素的数组被划分为三个元素和两个元素的子数组。三个元素的子数组进一步划分为一个元素和两个元素的子数组。然后将两个两个元素的子数组划分。
- 因此，"partition"方法将被调用四次。每个划分步骤至少需要两次交换，除了元素的比较和交换以及其他开销。当将所有工作加起来时，可以看到快速排序每次迭代需要做更多的工作。当迭代次数较少时，插入排序的总工作量较少。
- 可以通过逐步分析来确定理论上的"small"值，即插入排序将比快速排序更快的输入大小。通常，这是通过计算"基本操作"的数量来确定的，尽管定义有一定的灵活性。在这种情况下，很容易理解：比较、赋值或函数调用都是"基本操作"。
- 理论结果如何与实验结果相符取决于特定的计算机硬件，以及比较的开销如何。如果比较非常昂贵，那么您将希望选择执行最少数量比较的算法。但是，如果比较相对廉价（例如比较数字，甚至是字符串，前提是它们没有长的公共前缀），那么算法的开销将成为限制因素，并且简单而低效的算法将优于复杂而高效的算法。