排序算法快速排序与插入排序

Question

快速排序是一种O(nlog(n))排序算法。这是否意味着它总是比O(n2)算法的插入排序快？为什么/为什么不？

Answer 1

在极端情况下，快速排序和插入排序实际上可以具有与O(n)相同的性能。对于已经排序的集合的插入排序，插入一个新元素最多只需要进行O(n)比较，而且只需要使用O(1)进行插入。快速排序的最坏情况发生在分区总是导致一个元素后面跟着集合的其余部分时。如果这种情况一直持续到树下，那么在这种最坏的情况下，快速排序也可以在O(n)中运行。

然而，在一般情况下，我们预计quicksort将作为O(n*lgn)执行，而insertion sort将作为O(n^2)执行。

Answer 2

根据系统的不同，对于包含16到96个元素的小数组，插入排序可能会更快。Visual Studio将<= 32元素从快速排序或合并排序切换到插入排序。