我们可以进行n logn最坏情况复杂度的快速排序吗？
我想知道我们是否可以修改快速排序算法以产生O（n
logn）的最坏情况下的时间复杂度。尽管这可以通过置换数据然后假定我们将获得平均情况下的复杂性而不是最坏情况来完成。但这不是一个完整的解决方案，因为我们可以在置换后再次陷入最坏的情况。您还有其他建议吗？
回答：
好吧，是的，我们可以将其降低到O（nlogn）。我见过的所有尝试降低这一点的算法都基于选择枢轴点。如果您可以“智能地”选择枢轴点，则可以将其降低。
选项1.介绍排序。现在，它不再是一种“纯粹的”快速排序。稍后使用合并排序。2.选择中位数作为枢轴。现在，如果以通常的方式完成操作，找到中值可能会花费大量时间，但是算法介绍中有提及。
- 将数组分为[n / 5]个组，每个组有5个元素
- 使用插入排序找到每个组的中位数，然后从此列表中选择中位数
- 然后，您将需要递归尝试查找从每个组计算出的[n / 5]个中位数的中位数。
- 围绕该中位数对数组进行分区
我已经隐藏了该算法中一些更复杂的内容。如果需要，您可以在同一本书中阅读。通常，我不会尝试使用此算法。我使用随机选择操作来查找关键点并进行处理。
以上是 我们可以进行n logn最坏情况复杂度的快速排序吗？ 的全部内容， 来源链接： utcz.com/qa/403945.html
