预排序分析算法?

正如你所期望的,这里面有很多想法。三种技术的中位数意味着,对于已排序的数据,QuickSort的最坏情况不会出现,而是出现在不太明显的情况下。

Introsort 非常令人兴奋,因为它完全避免了QuickSort的二次最坏情况。与您自然提出的问题“我如何检测数据几乎已排序”不同,它实际上在进行过程中自问:“这需要太长时间吗?”。如果答案是“是”,它将从“快速排序”切换到“堆排序”。

Timsort 将合并排序与插入排序相结合,并在已排序或反向排序的数据以及包含已排序或反向排序的子集的数据上表现出色。

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

还有smoothsort,这显然很难实现,但是它在O(n log n)到O(n)之间有所不同,这取决于数据的排序方式。

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

长而复杂的PDF: http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF

但是,如果您的数据真的很大,并且您必须连续访问它,那么mergesort可能是最好的。它总是O(n对数N),并且具有极好的“位置”特性。

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

一种可能的解决方案是在当前排序范围内(在快速排序操作期间)采用第一个、最后一个和中间元素,并选择中间元素作为透视元素。

为了充分分析以决定使用哪种算法,您将要做的几乎是排序工作。您可以做一些类似的事情,以一小部分随机增加的索引来检查值(即分析一小部分项目样本)。

您仍然需要运行所有记录来确定其是否已排序,因此为了提高性能,从第一个记录开始,然后运行其余的记录,直到您注意到某些未正确排序的内容,或者到达列表的末尾。如果您发现丢失,则只对该位置到末尾的项目进行排序(因为列表的开头已经排序)。

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

快速排序只有当数据集很大并且已经大部分排序时,才会出现问题,我将使用以下启发式方法(等待完整的解决方案):

• 如果数据集大小低于阈值,则不必担心。

• 如果您对记录(项)具有快速(索引)访问权限,请在每n个记录中抽取一个记录为1的样本,并查看它们是否已经排序。对于一个小样本来说应该足够快,然后你可以决定是否使用快速排序。

提出一个人们尚未提出的概念性观点:快速排序是一种常识性的分而治之算法,在极少数情况下有明显的缺陷。假设你想整理一堆学生论文。(我必须做一些规律性的工作。)在快速排序算法中,您可以选择一些纸张,即轴。然后根据其他文件是在轴心之前还是之后进行划分。然后对这两个子文件重复这个步骤。虫子是什么?Pivot可以是一个靠近列表一端的名称,而不是中间的名称,因此将其分为两堆并不会完成很多工作。

合并排序是另一种按不同顺序工作的分治算法。您可以在线性时间内合并两个排序列表。将文件分成两个相等或几乎相等的堆,然后递归地对每个堆进行排序,然后合并。合并排序没有任何错误。快速排序比合并排序更受欢迎的一个原因是历史性的:快速排序(通常)很快,而且没有任何额外的内存。但是现在,保存比较比保存内存更重要,并且实际的重新排列通常是通过排列指针抽象出来的。如果事情总是这样,那么我怀疑合并排序会比快速排序更受欢迎。(也许在名字上加上“快点”是很好的销售技巧。)