我们可以做快速排序与正LOGN最坏情况下的复杂性？ [英] Can we do Quick sort with n logn worst case complexity?
问题描述
我在想，如果我们能以某种方式修改快速排序算法产生为O（n LOGN）的最坏情况下的时间复杂度。虽然这可以通过排列数据，然后假定我们会得到平均情况下的复杂性，而不是最坏的情况下进行。但是，这是不是一个完整的解决方案，证明我们能置换后再次降落到最坏的情况。是否有任何其他方式，你可以建议。
I was wondering if we can somehow modify the Quick sort algorithm to produce the worst case time complexity of O(n logn). Although this can be done by permuting data and then assuming that we will get the average case complexity rather than worst case. But this is not a full proof solution as we can again land into worst case after permuting. Is there any other way around that you can suggest.
推荐答案
嗯，是的，我们可以把它归结为O（nlogn）。我已经看到，试图把这个了所有的算法都是基于你的选择支点。如果你能聪明地选择你的支点就可以拿下来。
Well, Yes we can bring it down to O(nlogn). All the algorithms I have seen that try to bring this down are based on choosing your pivot point. If you can "intelligently" choose your pivot point it can be brought down.
选项 1. 介绍排序。它不再是一个纯粹的快速排序了。它使用归并排序以后。 2.选择位数作为一个支点。现在发现平均可能要花费大量的时间，如果在完成正常的方式，但有一个提到的算法导论。
Options 1. Intro Sort . It is no longer a "pure" quick sort now. It uses merge sort later on. 2. Choosing the median as a pivot. Now finding the median might take a huge amount of time if done in the normal way BUT there is a mention in the Introduction to Algorithms.
下面是一些直接从马的嘴算法导论
Here is something straight from the horse's mouth Introduction to Algorithms
- 除以数组[N / 5组，每组有5个元素
- 找到各组平均利用插入排序，然后从该列表中选择中值
- 然后，你将需要递归地尝试和发现中位数[N / 5]中位数从每组计算。
- 分区阵列解决此值
有一些更复杂的东西，这个算法，我已经隐藏研究。你可以通过它在同一本书，如果你想要的。通常情况下，我不尝试使用这种算法。我使用的是随机选择操作，找到支点并与工作。
There are some more complex stuff in this algorithm that I have hidden. You can go through it in the same book if you want. Usually, I don't try to use this algorithm. I use a randomized selection operation to find the pivot and work on with that.
这篇关于我们可以做快速排序与正LOGN最坏情况下的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
