logo标签列表

什么是确定性快速排序？

algorithmsortingquicksortdeterministic
11

我一直在研究快速排序，并发现有时它被称为“确定性快速排序”。

这是正常快速排序的另一个版本吗？正常快速排序和确定性快速排序之间有什么区别？

7个回答
14

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

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

快速排序的确定性版本和随机化版本有什么区别？ - Andreas Grech
2
确定性快速排序会确定地选择枢轴（例如，总是选择第一个未排序的元素或中间位置的元素）。随机化快速排序会随机选择未排序的元素作为枢轴。 - Anon.
1
主元素的选择。随机快速排序在数组中选择一个随机索引作为主元；确定性总是选择特定索引（即“最左侧”）。 - Billy ONeal
-1：回复并没有回答问题。不过评论中有解释。如果您编辑回复以回答问题，我会改为+1。 - Platinum Azure
我可以告诉你，没有更多的-1票了 ;) （顺便说一句，似乎删除-1票会忽略每天200声望上限...） - Anon.
显示剩余2条评论
10

快速排序的平均时间复杂度是 O(n log n)，但最坏情况下会达到 O(n^2)。这种情况通常发生在选择的枢轴元素始终为最小值或最大值时。

理想情况下，我们希望选择中位数作为枢轴元素。如果直接查找中位数的代价太高（通常是因为你正在尝试使用快速排序），则通常会选择以下两种方法之一：要么选择三个潜在的枢轴元素的中位数，要么随机选择一个元素作为枢轴。

后一种方法使快速排序变得不确定，因为枢轴元素选择过程中存在随机性。

1
另外，我认为值得一提的是，与您在问题中所要求的相反，确定性快速排序往往是“正常”的快速排序，至少就教学而言，因为它最简单。随机枢轴通常是在实现时做出的决策，希望提高算法的整体性能。 - Platinum Azure
4

通常情况下，如果一个排序算法每次都能按照相同的顺序排序元素，则被称为“确定性”的。给定一组要按id（升序）排序的记录：

  1 Censu
  11 Marju
  4  Cikku
  11 Lonzu

如果使用排序算法，可能会返回Censu、Cikk、Marju、Lonzu或Censu、Cikku、Lonzu、Marju这样的正确排序。确定性排序是一种总是返回相同顺序的排序方式。但这不总是适用的。在快速排序中，如果随机选择枢轴（理想情况下应该选择中位数，但这可能代价高昂），可以获得更快的平均性能。然而，这是有代价的：您的搜索不再是确定性的。

1
我认为你在考虑“稳定”的排序算法。 - Martin
搜索不再稳定（快速排序本来就不稳定吗？），但它仍然会按照您的比较函数定义的“排序”顺序返回元素。这并不像随机选取枢轴会使快速排序只有一半时间正常工作，或者其他什么东西。 - Platinum Azure
3
@Martin：稳定排序是确定性的，但反之不一定成立。为了使排序稳定，同等值的条目必须保持它们最初给出的顺序。确定性排序不需要这样做，但返回的顺序必须始终相同。 - Il-Bhima
@Platinum Azure。无论是“标准”还是随机化的快速排序，都能始终正确地工作。关键是对于具有相等比较键的条目会发生什么情况。 - Il-Bhima
1
@Il-Bhima：我从未说过相反的话。稳定性是指具有相等比较键的条目。我的问题是，你似乎把“确定性”和“稳定性”混为一谈；这两者并不相同。 - Platinum Azure
哇，我从未知道！我喜欢 Stack Overflow，因为它每天都能教我一些新的有趣的东西:D - Martin
1

在快速排序中，常见的形容词有确定性和随机化。确定性意味着快速排序始终以相同的方式对相同的数据集进行排序，而随机化快速排序则使用随机化，并且很少以完全相同的方式对相同的数据进行排序（除非数据集非常小 - 那么这种情况更为普遍）。

确定性

关键在于如何选择枢轴。在确定性快速排序中，枢轴的选择是通过选择相同相对位置的枢轴，例如第一个、最后一个或中间元素，或者使用任意数量预定元素的中位数来实现。例如，一种常见的方法是选择第一个、最后一个和中间元素的中位数作为枢轴。即使使用我刚才描述的中值法，某些数据集也很容易产生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)时间复杂度的可能性，但概率要小得多，并且随着数据集大小的增加而变得更小。

1

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

1

这与分区有关（或者是著名的快速排序中使用的分治法中的划分步骤）。如果每次将最后一个（或第一个元素或任何位置的元素，只要在每次划分数据集时使用相同的位置）用作枢轴进行分区，则为确定性快速排序。如果随机选择枢轴，则为随机化快速排序。

这里有一份讲义笔记，可以帮助理解。

希望对您有所帮助。

祝好

0

除了其他人已经告诉你的关于如何实现确定性快速排序和非确定性快速排序的内容之外，我认为这种排序更重要的一个方面是，在确定性快速排序中，当键冲突时，记录的顺序总是相同的，而在非确定性快速排序中，这些记录的顺序每次运行排序时可能会不同。

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

但是快速排序默认情况下并不稳定，让它既稳定又快并不是一件简单的任务，所以这真的很重要吗？ - IVlad
@|/|ad：不确定我是否理解了...有很多使它稳定的方法，但这意味着需要更多的计算能力（时间）......然而，当分区被确定地选择时，结果集总是按相同的顺序排列...是吗？（我开始怀疑我的答案了） - Bruno Brant
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接