我正在比较插入排序和快速排序。我已经弄清楚了为什么快速排序在近乎有序的数组上速度较慢，但是我无法理解为什么插入排序要快得多，因为它仍然需要比较数组中几乎相等数量的元素。
5个回答
4
插入排序在已排序或接近排序的数组上更快的原因是，当它将元素插入到已排序部分时，它几乎不需要移动任何元素。例如，如果数组的已排序部分是
1 2，下一个元素是3，它只需要进行一次比较--2 < 3--就可以确定它根本不需要移动3。因此，对于已经排序的数组，插入排序是线性时间，因为它每个元素只需要进行一次比较。- Louis Wasserman
1
这取决于几个因素。对于小数据集，插入排序比快速排序更有效率。它还取决于您的后备列表实现（LinkedList或ArrayList）。最后，它还取决于输入数据是否有任何排序方式。例如，如果您的输入数据已按相反顺序排序并使用LinkedList，则插入排序将非常快。
- mprivat
0
快速排序在已经排序好的数组上具有最坏情况（O(n^2)时间复杂度）（参见维基百科中的快速排序条目）。
根据选择的轴元素，这可以在一定程度上缓解，但与此同时，插入排序的最佳情况恰好是预排序的情况（对于这种输入，它的时间复杂度为O(n)），所以在这个特定的用例中，它将胜过快速排序。
- Alan
0
插入排序算法在已排序的数组上以线性时间运行，因为对于已排序的数组，插入排序只需要进行一次比较，即与前一个元素比较，因此在已排序的数组上进行插入排序只需线性移动，复杂度为O(n)。 与快速排序相比，其复杂度为O(n2)。
- Shivamyadav37
-1
排序后的输入对于插入排序是最佳情况(O(n))，而对于快速排序则是最坏情况(O(n^2))。
这与复杂度有关，复杂度由键比较的数量决定，这是两种算法的基本操作。
因此当你查看这两种算法时，你会发现在插入排序中，您只需要进行n次比较，因为当我们插入一个元素时，我们只与左侧元素进行比较即可。另一方面，在快速排序的情况下，您必须将您的支点元素与所有左侧元素进行比较，您的数组会以一个恒定的因素减少，导致近似n^2次比较。
- Arjun Chaudhary
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接