11

我一直在阅读有关快速排序的文章，发现有时它被称为“确定性快速排序”。

这是普通 Quicksort 的替代版本吗？普通快速排序和确定性快速排序有什么区别？

4

7 回答 7

13

普通（“确定性”）快速排序在特定数据集上的行为可能非常差（例如，选择第一个未排序元素的实现在已排序的数据上具有 O(n^2) 时间复杂度）。

随机快速排序（选择随机枢轴，而不是确定性选择）有时用于在所有数据集上提供更好的预期性能。

于 2010-02-22T20:33:46.187 回答
10

快速排序在O(n log n)预期/平均时间运行，但在O(n^2)最坏的情况下。如果选择的枢轴始终是最小值或最大值，则会发生这种情况。

理想情况下，您希望选择中位数作为您的支点。如果直接找到中位数成本太高（如果您尝试使用快速排序，通常就是这种情况），通常做的是取三个潜在枢轴元素的中位数，或者只选择一个随机元素作为枢轴.

由于枢轴选择过程固有的随机性，后一种方法呈现快速排序的不确定性。

于 2010-02-22T20:35:45.823 回答
4

一般来说，如果排序算法每次都以完全相同的顺序对元素进行一致的排序，那么它就是“确定性的”。给定一组要按 id (asc) 排序的记录：

  1 Censu
  11 Marju
  4  Cikku
  11 Lonzu

那么排序算法可以将 Censu、Cikk、Marju、Lonzu 或 Censu、Cikku、Lonzu、Marju 作为正确排序返回。确定性排序总是返回相同的排序。不一定总是如此。在快速排序的情况下，如果随机选择枢轴，可以获得更快的平均性能（理想情况下，您会选择中位数，但这可能会很昂贵）。然而，这是有代价的：您的搜索不再是确定性的。

于 2010-02-22T20:46:21.107 回答
1

您的来源可以（并且应该）给出自己的定义，但通常确定性快速排序是通过不依赖于随机数的公式选择枢轴的方法。例如，总是选择中间元素或总是第一个，或者类似的东西。这意味着无论您在相同的输入上运行多少次，它的性能都将始终相同（理论上无论如何，尽管实际上差异不应太大）。随机快速排序意味着您在选择枢轴时使用随机数，这意味着无法（轻松）预测同一输入上不同运行的性能。

于 2010-02-22T20:37:05.090 回答
1

它与分区（或快速排序中使用的著名分治法中的分步）有关。如果每次将最后一个（或第一个元素或任何位置的元素，只是每次划分数据集时都必须是相同的位置）用作分区的枢轴，那么它就是确定性快速排序。如果枢轴是随机选择的，则它是随机快速排序。

这是一个讲义，它说明了这一点。

我希望它有帮助

干杯

于 2010-02-22T20:37:29.253 回答
1

快速排序前面的常用形容词是确定性的和随机的。确定性意味着快速排序将始终以相同的方式对相同的数据集进行排序，而随机快速排序使用随机化并且很少以相同的确切方式对相同的数据进行排序（除非数据集非常小 - 然后更常见） .

确定性

这取决于如何选择支点。在确定性快速排序中，通过始终选择相同相对索引处的枢轴（例如第一个、最后一个或中间元素）或使用任意数量的预定元素选择的中值来选择枢轴。例如，一种常见的方法是选择第一个、最后一个和中间元素的中值作为枢轴。即使使用我刚刚描述的中值 3 方法，某些数据集也很容易给出 O(N^2) 时间复杂度。一个示例数据集是所谓的风琴管数据集：

array = [1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2,1]

随机的

随机快速排序可以只选择一个随机枢轴或使用一些随机选择的枢轴的中位数。仍然存在 O(N^2) 时间复杂度的可能性，但概率会小得多，并且随着数据集大小的增加而变得更小。

于 2010-02-22T21:03:44.550 回答
0

除了许多其他人已经告诉过你的关于如何实现确定性快速排序和非确定性快速排序之外，我相信这种排序的一个更重要的方面是，使用确定性快速排序，你总是有相同的顺序键冲突时的记录，而使用非确定性快速排序时，每次运行排序时此类记录的顺序可能不同。

我想当你有非唯一键时，你不应该使用非确定性快速排序。

于 2010-02-22T20:49:03.023 回答