预排序分析算法？

这是一个众所周知的与Quicksort isssue，当数据集处于或几乎排序，性能下降可怕。在这种情况下，Insertion Sort（通常非常缓慢）很容易成为最佳选择。问题是知道何时使用哪个。预排序分析算法？

是否有算法可用于运行数据集，应用比较因子并返回数据集按照排序顺序接近的报告？我更喜欢Delphi/Pascal，但如果示例不是太复杂，我可以阅读其他语言。

2009-12-04 Mason Wheeler

如果实现对于选择元素元素来说太简单，那么使用预排序序列的快速排序的缓慢性只是一个问题，AFAIK。例如，请参阅http://www.cprogramming.com/tutorial/computersciencetheory/quicksort.html。 – Dirk 2009-12-04 20:06:41

正如您所期望的那样，我们有很多想法。三中位数技术意味着排序数据不会出现快速排序的最坏情况行为，而是出现不太明显的情况。

Introsort是相当令人兴奋的，因为它完全避免了quicksort的二次最坏情况。与其自然而然的问题不同，“我如何检测数据几乎被排序”，它实际上是在问自己是否正在进行，“这是否花了太长时间？”。如果答案是肯定的，它会从快速排序切换到堆排序。

Timsort将合并排序与插入排序组合在一起，并且对排序或反向排序数据以及包含排序或反排序子集的数据执行得非常好。

所以你的问题的答案可能是“你不需要预分析，你需要一个自适应排序算法”。

来源

2009-12-04 20:49:42

+1 timsort链接 – 2009-12-04 21:10:45

+1哇，timsort看起来很整洁。 – wowest 2009-12-04 21:28:25

我还没有听说过任何预分拣分析，但我的观点是，如果你要通过数据集来分析它，那么你已经在削减整体分拣时间的表现。

来源

2009-12-04 20:07:22 martinatime

这是一个很好的观点，但如果分析过程是O（n），它将不会支配渐近分类时间。如果它可以帮助避免O（n^2）最差情况下的排序时间，那么对于大型数据集的排序时间可能是一个净效益。 – ddaa 2009-12-04 20:14:07

@ddaa：对于比较排序，这是正确的，但是使用基数排序或排序排序可以进行O（n）排序。如果我们包含这些算法，排序时间可能会受到分析时间的支配...... – 2009-12-04 20:28:48

@Jason：您不会对您即将进行排序的数据执行此分析。问题是关于快速排序和插入排序之间的选择，并且你打算不这样做...... – 2009-12-04 20:59:25

一种可能的解决方案是在当前排序范围内（QuickSort操作期间）取第一个，最后一个和中间元素，并选择中间元素作为主元素。

来源

2009-12-04 20:13:27 gabr

你最好的情况仍然是O（N日志N），其中插入排序是O（N）几乎排序的数据。 – wowest 2009-12-04 20:15:13

为了充分分析决定使用哪种算法的目的，你将要做几乎排序的工作。你可以做一些事情，比如检查一小部分随机但增加的索引值（即分析一小部分项目）。

来源

2009-12-04 20:13:35

还有SmoothSort，这显然是相当棘手的实现，但它取决于数据的排序方式从O（N log N）到O（N）之间的变化。

http://en.wikipedia.org/wiki/Smoothsort

朗棘手PDF： http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF

然而，如果你的数据确实是巨大的，你必须连续访问它，归并可能是最好的。它始终是O（N log N），它具有出色的“局部性”属性。

来源

2009-12-04 20:14:25 wowest

您仍然需要遍历所有记录以确定它是否已排序，以便提高性能，从第一条记录开始并运行，直到您发现某些未正确排序的内容或达到列表。如果您发现错过，那么只会将该位置的项目排序到最后（因为列表的开头已经排序）。

在第二部分的每个项目中，查看该项目是否为<，而不是第一部分的最后一个元素，如果是这样，则仅对第一部分使用插入排序。否则，快速排序第二部分中的所有其他项目。这种方式是针对特定情况进行优化的。

来源

2009-12-04 20:38:25 skamradt

快速排序绷只有当数据集是巨大的，已经大多排序，我会用下面的启发式（一个完全成熟的解决方案待定）一个问题：

如果数据集大小不要打扰低于阈值。
如果您对记录（项目）有快速（索引）访问权限，请在每N条记录中记录一条记录，并查看它们是否已经排序。对于小样本应该足够快，然后您可以决定是否使用快速排序。

来源

2009-12-04 20:48:48

但如果每个N中有1条记录排序，则样本失败，但是每N个记录中的+1记录不是。您可能仍然需要阅读每条记录，看看其中一个未采样是否出现故障。 – skamradt 2009-12-04 21:40:43

同意，但统计上很少有机会，样本会偏离整体人群，尤其是如果你随机化了一点N. – 2009-12-05 00:34:28

为了提出人们还没有做出的概念性观点：Quicksort是一种常见的分而治之算法，在极少数情况下具有明显的缺陷。假设你想分类一堆学生论文。（我必须处理一些规律性问题。）在快速排序算法中，您选择一些纸张，即关键点。然后根据是否在数据透视之前或之后划分其他文件。然后用这两个子文件重复一遍。什么是错误？关键点可能是一个靠近列表的一端而不是中间的名称，因此将它分成两堆并不是很成功。

合并排序是另一种分而治之算法，它以不同的顺序工作。您可以在线性时间合并两个排序列表。将论文分成两个相等或几乎相等的纸堆，然后递归排序，然后合并。合并排序没有任何错误。快速排序比合并排序更受欢迎的一个原因是历史性的：Quicksort速度很快（通常），而且它没有任何额外的内存。但是现在，保存比较比保存内存更重要，实际的重新排列通常是通过排列指针来提取的。如果事情总是如此，那么我怀疑合并排序只会比快速排序更受欢迎。（也许在名称中加入“quick”是很好的推销手段。）

来源

2009-12-06 23:00:29

从我的POV中，就地排序的好处并不在于它节省了*内存*，因为它节省了内存分配，因此不会失败。所以当对一个数组进行排序时，quicksort/heapsort /插入排序/冒泡排序都具有比mergesort更好的用户界面。如果mergesort比快速排序更受欢迎，那么当然你可以尝试分配内存，如果失败了，可以改为快速排序。如果你正在分配一个辅助数组指针并对其进行排序，那么你正在引入失败的可能性，因此可能允许在别处失败。 – 2012-07-09 09:21:26

@SteveJessop这是一个公平的观点。然而，这种担忧虽然在某些情况下仍然很重要，但也有些过时。我同意，外部环境公平分配内存给每个需要它的客户端程序或函数是不平凡的。然而，即使是在很多环境下，这种情况也会随着时间的推移而变得更好。 – 2012-12-04 15:22:25

我不认为这是一个真正的公平问题，就像您用完时发生的情况一样，以及您是否对此感觉强劲。如果分配失败，那么你可以单独编写程序。如果操作系统将水冲出来，直到它有足够的内存来满足第一次访问请求或页面错误，那么您可以用另一种方式编写程序。有些语言会走中间路径，理论上你可能会发现内存不足的异常并继续，但在实践中你不会这样做，你会让异常杀死你。我想这可以被认为是“最新”的方式来做到这一点;-) – 2012-12-04 16:53:23

预排序分析算法？

回答

相关问题