有人可以解释为什么快速排序的最佳运行时间不是线性的吗?有没有办法使快速排序的最佳运行时间成为线性的?如果是这样,为什么它们通常不在实践中使用?
问问题
174 次
4 回答
1
您至少应该浏览过 wiki 链接......他们用图表和动画进行了解释,这很容易理解。
于 2013-02-26T07:23:28.293 回答
0
快速排序是一种直接比较排序方法。每个这样的方法在每个步骤上都使用二元决策(即直接比较)以在排序的两个可能结果之间进行分支。N 个元素的数组所有可能的排序都是 N! 因此,能够输出这些结果中的每一个的二叉决策树的最低高度是 log(N!),它可以被证明,尽管不是很容易证明 O(log(N!)) = O(N*日志(N))。因此,没有任何直接比较排序算法的复杂度可能比这更好。
因此,由于快速排序是此类算法的一个示例,它的复杂度永远不会低于 O(N*log(N)),因此它不能是线性的。
于 2013-02-26T09:02:11.760 回答
0
快速排序在 O(n 2 ) 时间最坏情况下运行,但最佳/平均 O(n log n)。尽管它的最坏情况更高,但在实践中它通常优于堆排序和归并排序(最坏情况 O(n log n) 排序)。
除非它们已经排序,否则排序只能在线性时间内运行,这仅适用于具有最佳情况 O(n) 的排序,例如插入排序。
于 2013-02-26T07:30:32.823 回答
0
当然你可以先检查输入是否已经排序,如果是则立即返回。这产生了具有线性最佳情况复杂度的算法。但是你最终会得到一个“修改过的快速排序”而不是“快速排序”。
于 2013-02-26T07:32:43.533 回答