logo标签列表

修改后的快速排序算法能够在最优情况下达到O（n）的时间复杂度吗？

javaalgorithmsortingbig-oquicksort
3
一般认为，快速排序的最佳情况是O(nlogn)，假设每次分区时数组大致上被划分了一半。同时，最坏情况是n^2阶，如果数组已经被排序。我们能不能通过设置一个名为swap的布尔值来修改快速排序呢？例如，如果第一次遍历中没有初始交换位置，那么我们可以假设数组已经被排序，因此不需要进一步分区数据。我知道改进后的冒泡排序使用了这种方法，通过检查交换，让最佳情况变成了O(n)，而不是O(n^2)。这种方法能否应用于快速排序呢？为什么？
你也可以尝试在http://cstheory.stackexchange.com上询问。 - 9000
1
你可以通过在开始时检查数组是否已排序，使得任何排序方法在最佳情况下达到O(n)。你想了解这个吗？ - sdcvvc
8
9000：不，cstheory是用于更高级问题的。 - sdcvvc
考虑到有更好的最坏情况性能和O(n)最佳情况的排序方法，这听起来非常理论化。 - user12861
@9000：更具体地说，CSTheory 是针对研究级别的内容。而这则是本科/家庭作业级别的内容。 - hugomg
2
你可以通过在执行任何操作之前检查数组是否已经排序来使任何排序算法在最佳情况下达到O(n)。 - user97370
3个回答
5

你的方法有一个错误...

例如我们有这样一个数组:

1243 5 678

我们的基准元素是 5。第一次遍历后不会进行交换（因为4和3都比它小），但是数组并没有排序。所以你必须开始划分，这导致了n log n的时间复杂度。

有道理。由于我们只检查左侧是否小于基准元素，这并不总是意味着所有内容都是按顺序排列的。那么，我可以正确地假设，在快速排序中，无论如何修改，最佳情况都是O（nlogn）吗？ - Kira
是的，有一个数学证明表明，排序算法的最佳情况必须是nlogn。 - Sebastian Oberste-Vorth
2
不，这并不能用于快速排序。在冒泡排序中，如果你对数组进行一次遍历而没有进行任何交换，那么你就知道整个数组已经排序。这是因为在冒泡排序中，每个元素都与其相邻元素进行比较，因此在任何没有进行交换的遍历之后，你可以推断整个数组已经排序。
但是，在快速排序中情况并非如此。在快速排序中，每个元素都只与单个枢轴元素进行比较。如果你在进行整个遍历的时候没有移动任何元素，那么这只能告诉你这些元素相对于枢轴是有序的（小于枢轴的值在其左侧，大于枢轴的值在其右侧），而并不能告诉你它们彼此之间是否有序。
一些修改后的版本可以完全通过数组（没有枢轴）并检查它是否已排序，但经典的快速排序则不能。 - bestsss
@bestsss 那是一个单独的检查。我认为 OP 的意思是使用快速排序的正常初始扫描来检查是否已排序。 - Bill the Lizard
0
此外，还存在一个问题，即在几乎排序的数组中，除了完全排序的输入之外，您也会得到O(n)的行为。
您可以尝试更努力地使您的方法起作用，但我认为您无法突破O(n log n)的界限。有一个证明表明，在最坏情况下，基于比较的排序不能比O(n log n)更有效率。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接