我真的不明白为什么我们不总是选择中值元素作为枢轴。这可以在 O(n) 中完成，因此总运行时间为 O(n log n)。
我只是假设中值搜索的 O(n) 中可能隐藏了一个很大的常数。
问问题
2750 次
3 回答
7
相反，一旦我们知道最坏情况选择算法可用，我们就可以使用它在快速排序的每一步中找到理想的枢轴（中位数），从而产生运行时间为最坏情况 O(n log n) 的变体。然而，在实际实现中，这种变体平均要慢得多。
换句话说，强制它保证 O(n log n) 的成本通常不值得付出。该页面以及选择算法页面上有更多信息。
于 2011-03-31T06:33:50.913 回答
0
使用随机快速排序，您的 O(n log n) 的最坏情况运行时间的概率非常高。
于 2011-03-31T14:47:36.457 回答
0
显然，使用随机版本的分区，找到中位数的运行时间似乎是 O(n)，但实际上，当分区再次在其极端不平衡时，运行时间会变为 O(n 2 )。所以你不能从这里做任何改进。但还是有希望的。如果您通过“CORMEN”，那么您会发现即使在最坏的情况下，也可以在线性时间内找到第 i 个顺序统计量。使用的技术是使用中位数的中位数作为枢轴元素，然后找到在任何情况下都能保证线性运行时间的中位数。所以我们也可以在快速排序中使用该技术来获得 O(nlgn) 运行时间
于 2012-08-17T14:16:30.027 回答