使用枢轴中间元素在最坏情况下快速排序复杂性
因为最坏情况下的快速排序复杂度为O（n^2）
在递增顺序的情况下，当pivot选择第一个或最后一个元素时，它给出了正确的最坏情况复杂度O（n^2），因为树的一个子元素总是空的
但是当枢轴选择中间时，我感到困惑？它将树分成两半，使其复杂性O（n.logn）
假设10 20 30 40 50 60 70枢轴=40
(10 20 30 ) 40 (50 60 70)
左侧枢轴20，右侧枢轴60
(10) 20 (30)
（50）60（70）
正确吗？？？？
共有3个答案
当选择一个透视时，列表被分区，因此透视左侧的元素比透视小，右侧的元素比透视大。至此，排序问题并没有像你描述的那样一分为二。
选择透视后，您需要对左右分区进行排序。这将涉及为每一个选择一个新的枢纽和分区。快速排序递归进行，直到只有一个左右分区。
我建议查看快速排序算法，并从头到尾手动浏览几个示例。
如果你是视觉学习者，下面的动画会对你有所帮助:http://www.csanimated.com/animation.php?t=Quicksort
关键是您正在从未排序的数组中选择轴点。所以值是随机的。例如，如果您碰巧每次都选择最低的值，则分区左侧将没有任何内容。这意味着右边的每个递归调用将比前一个调用少处理一个元素。粗略地说，这些调用完成的总工作将是O（sum（i）for i=n多谢1）=O（n^2）。
在您的示例中，您假定要排序的列表已排序。
在这种情况下，当您总是选择第一个或最后一个项目作为枢纽时，快速排序确实会执行O(n^2。
如果你选择中间的项目，它当然有可能会有不好的表现。例如：
1 2 3 4 (5) 1 2 3 4
现在，由于没有高于5的项目，这是一个糟糕的支点，尽管它是一个中间元素。
因为对排序列表进行排序是一种常见的情况，所以使用第一个或最后一个项目作为数据透视被认为是一种糟糕的做法。一般来说，中间项目不太可能是一个糟糕的支点。
-
我想展示Quicksort空间复杂性的最坏情况。 我在想它，快速排序不使用辅助数组，它只是在分区子程序上创建一些辅助变量，但它只是操作数组中的项目。所以，很明显，我的结论是它使用了O（n）空间。 但我在网上搜索发现，Quicksort在最坏情况下的空间复杂度为O（logn）。 我只是不明白为什么在最坏的情况下，它比输入数组占用的空间更少？ ps：我在看《算法导论》这本书。 我已经尝试的是计算算法中
-
null
-
我试图实现就地快速排序，最后一个元素作为我的支点。下面附上我的代码 出于某种原因，我的代码给了我一个IndexOutOfBounds异常，它不能准确地对数组排序。我不知道为什么会出现这个错误。 如果我理解正确，我们应该把最后一个元素作为我们的轴心。然后，我们将左指针向右迭代，直到找到一个大于枢轴的元素。之后，我们从右侧（继续向左移动）执行相同的操作，直到找到一个小于轴的元素。然后我们交换这些元素，
-
本文向大家介绍快速排序的最优情况？相关面试题，主要包含被问及快速排序的最优情况？时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 快速排序的最优情况是Partition每次划分的都很均匀,当排序的元素为n个,则递归树的深度为。在第一次做Partition的时候需对所有元素扫描一遍,获得的枢纽元将所有元素一分为二,不断的划分下去直到排序结束,而在此情况下快速排序的最优时间复杂度为。
-
尝试使用Hoare分区方案实现快速排序，但我遇到了一个问题，即无论数组大小如何，更改pivot的索引都会导致溢出。代码： 这个实现选择低索引（这里名为min）作为轴心元素，这样做很好。但是，将pivot元素更改为任何其他索引都会导致StackOverflow错误，而与正在排序的数组的大小无关。（错误参考第3行，其中调用了partition（））我最好在（min，max）范围内随机选择pivot元素
-
我有一个关于计算时间复杂度的非常普遍的问题（大O符号）。当人们说QuickSort最差的时间复杂度是O（n^2）（每次都选择数组的第一个元素作为轴心，并且数组是反向排序的）时，他们考虑了哪个操作来获得O（n^2）？人们会计算if/else语句所做的比较吗？或者他们只计算其进行的互换的总数？一般来说，你如何知道计算大O符号需要计算哪些“步骤”。 我知道这是一个非常基本的问题，但我已经阅读了谷歌上几乎