8

Quicksort 的一个众所周知的问题是，当数据集处于或几乎处于排序顺序时，性能会严重下降。在这种情况下，通常非常慢的插入排序很容易成为最佳选择。问题是知道何时使用哪个。

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

4

8 回答 8

10

正如您所期望的那样，对此进行了很多思考。3 的中值技术意味着快速排序的最坏情况行为不会发生在已排序的数据中，而是发生在不太明显的情况下。

Introsort非常令人兴奋，因为它完全避免了快速排序的二次最坏情况。而不是你的自然问题，“我如何检测到数据接近排序”，它实际上在问自己，“这需要太长时间吗？”。如果答案是肯定的，它会从快速排序切换到堆排序。

Timsort将归并排序与插入排序相结合，在排序或反向排序的数据以及包含排序或反向排序子集的数据上表现得非常好。

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

于 2009-12-04T20:49:42.977 回答
3

还有 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-04T20:14:25.110 回答
0

我没有听说过任何预排序分析，但我的观点是，如果您要通过数据集进行分析，那么您已经在削减整体排序时间的性能。

于 2009-12-04T20:07:22.173 回答
0

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

于 2009-12-04T20:13:27.080 回答
0

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

于 2009-12-04T20:13:35.847 回答
0

您仍然需要遍历所有记录以确定其是否已排序，因此为了提高性能，请从您的第一条记录开始并运行其余记录，直到您发现某些未正确排序或到达列表末尾。如果您发现未命中，则仅将项目从该位置排序到末尾（因为列表的开头已经排序）。

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

于 2009-12-04T20:38:25.930 回答
0

只有当数据集很大并且已经大部分排序时，快速排序才会出现问题，我会使用以下启发式方法（等待一个完整的解决方案）：

  • 如果数据集大小低于阈值，请不要打扰。

  • 如果您可以快速（索引）访问记录（项目），请在每 N 条记录中抽取 1 条记录的样本，并查看它们是否已经排序。对于小样本应该足够快，然后您可以决定是否使用快速排序。

于 2009-12-04T20:48:48.343 回答
0

To make a conceptual point that people haven't yet made: Quicksort is a common-sense divide-and-conquer algorithm with an obvious bug in rare cases. Suppose that you want to sort a stack of student papers. (Which I have to do with some regularity.) In the quicksort algorithm, you pick some paper, the pivot. Then divide the other papers according to whether they are before or after the pivot. Then repeat that with the two subpiles. What's the bug? The pivot could be a name that is near one end of the list instead of in the middle, so that it doesn't accomplish much to divide it into two piles.

Merge sort is another divide-and-conquer algorithm that works in a different order. You can merge two sorted lists in linear time. Divide the papers into two equal or nearly equal piles, then recursively sort each one, then merge. Merge sort doesn't have any bugs. One reason that quicksort is more popular than merge sort is historical: Quicksort is fast (usually) and it works without any extra memory. But these days, it can be more important to save comparisons than to save memory, and the actual rearrangement is often abstracted by permuting pointers. If things had always been that way, then I suspect that merge sort would simply have been more popular than quicksort. (And maybe adding "quick" to the name was good salesmanship.)

于 2009-12-06T23:00:29.220 回答