java - 为什么插入排序比排序数组上的快速排序快

Question

我正在将插入排序与快速排序进行比较。我已经弄清楚为什么 qsort 在几乎排序的数组上速度较慢，但​​我无法弄清楚为什么插入排序要快得多，当然它仍然需要比较数组中几乎一样多的元素？

Answer 1

插入排序在已排序或接近排序的数组上更快的原因是，当它将元素插入到数组的已排序部分时，它几乎不需要移动任何元素。例如，如果数组的排序部分是1 2并且下一个元素是3，它只需要进行一次比较——2 < 3确定它根本不需要移动3。因此，对已排序数组的插入排序是线性时间的，因为它只需要对每个元素进行一次比较。

Answer 2

这取决于几个因素。插入排序将比对小型数据集的快速排序更有效。它还取决于您的后备列表实现（LinkedList 或 ArrayList）。最后，它还取决于输入数据是否有任何排序。例如，如果您的输入数据已经以相反的顺序排序并且您使用 LinkedList，则插入排序将非常快。

Answer 3

快速排序在已经排序的数组上具有最坏的情况（O(n^2) 时间复杂度）（参见Wikipedia 上的快速排序条目）。

根据枢轴元素的选择，这可以在一定程度上得到缓解，但同时，插入排序的最佳情况正是预排序的情况（对于此类输入，它具有 O(n) 时间复杂度），所以它对于这个特定的用例，它将击败快速排序。

Answer 4

插入排序算法在已排序数组上以线性时间运行，因为对于已排序数组，插入排序只需进行一次比较，即针对前一个元素，因此已排序数组上的插入排序必须线性移动，达到复杂度为 - O(n)。与复杂度为 O(n2) 的快速排序相比

Answer 5

排序后的输入是插入排序的最佳情况（O（n））和快速排序的最坏情况（O（n ^ 2））。

这一切都与复杂性有关，复杂性由密钥比较的数量决定，这是两种算法的基本操作。

因此，当您看到两者的算法时，您会发现在插入排序中您只有 n 比较，因为当我们插入一个元素时，我们只与左元素进行比较并完成。另一方面，在快速排序的情况下，您必须不断将您的枢轴元素与所有左侧元素进行比较，并且您的数组类型会减少一个常数，导致大约 n^2 比较。