pse*_*ode 7 sorting algorithm quicksort
我想知道我们是否能以某种方式修改快速排序算法以产生O(n logn)的最坏情况时间复杂度.虽然这可以通过置换数据然后假设我们将得到平均情况复杂度而不是最坏情况来完成.但这不是一个完整的证明解决方案,因为我们可以在置换后再次陷入最坏的情况.你有什么别的建议吗？
S.P*_*.P. 15
好吧,是的,我们可以把它归结为O(nlogn).我所看到的所有尝试降低这些算法的算法都是基于选择您的支点.如果您可以"智能地"选择枢轴点,则可以将其降低.
选项1. 简介排序.它现在不再是"纯粹的"快速排序.它稍后使用合并排序.2.选择中位数作为支点.现在找到中位数可能会花费大量时间,如果以正常方式完成,但在算法导论中有提及.
这是马的嘴直接算法
我隐藏了这个算法中有一些更复杂的东西.如果你愿意,你可以在同一本书中阅读.通常,我不会尝试使用此算法.我使用随机选择操作来找到枢轴并继续使用它.