快速排序与插入排序

Question

在构建排序算法对数组进行排序时，数组中有多少n个元素的排序速度比插入排序快？我知道快速排序适用于更多的元素，而插入排序适用于较小的元素。但是想知道Quick Sort的大小比插入排序好得多吗？

Answer 1

这些算法不仅仅依赖于数组的大小来确定它们的运行时间。对于快速排序，您的算法选择的轴会对运行时产生重大影响。如果透视始终是最大或最小的元素，则快速排序采用O(n^2)。除了数组大小之外，插入排序还受到其他因素的影响。如果按顺序插入元素，则无论数组大小如何，算法都可能允许运行时为O(n)。但是，如果您以相反的顺序插入，则此算法将采用O(n^2)。由于这些因素，不存在保证一种算法比另一种算法执行得更好的大小n。如果你关心大型数组的排序算法的运行时，你应该查看堆排序或合并排序，它们都是O(n log n)，而且速度更快！