我们可以进行n logn最坏情况复杂度的快速排序吗？

我们可以进行n logn最坏情况复杂度的快速排序吗？

好吧，是的，我们可以将其降低到O（nlogn）。我见过的所有尝试降低这一点的算法都基于选择枢轴点。如果您可以“智能地”选择枢轴点，则可以将其降低。

选项1.介绍排序。现在，它不再是一种“纯粹的”快速排序。稍后使用合并排序。2.选择中位数作为枢轴。现在，如果以通常的方式完成 *** 作，找到中值可能会花费大量时间，但是算法介绍中有提及。

1. 将数组分为[n / 5]个组，每个组有5个元素
2. 使用插入排序找到每个组的中位数，然后从此列表中选择中位数
3. 然后，您将需要递归尝试查找从每个组计算出的[n / 5]个中位数的中位数。
4. 围绕该中位数对数组进行分区

我已经隐藏了该算法中一些更复杂的内容。如果需要，您可以在同一本书中阅读。通常，我不会尝试使用此算法。我使用随机选择 *** 作来查找关键点并进行处理。