我刚想到,如果你对要排序的数据的分布(在统计意义上)有所了解,那么如果考虑到这些信息,排序算法的性能可能会受益 .
所以我的问题是,是否有任何排序算法考虑到这种信息?他们有多好?
编辑:一个示例澄清:如果您知道数据的分布是高斯分布,则可以在处理数据时动态估计平均值和平均值 . 这将为您估算每个数字的最终位置,您可以使用它来将它们放置在最终位置附近 .
编辑#2:我很惊讶答案不是一个维基链接到一个讨论这个问题的页面 . 这不是一个非常常见的情况(例如高斯情况)?
编辑#3:我正在为这个问题增加一笔赏金,因为我正在寻找明确的答案来源,而不是猜测 . 类似于“在高斯分布式数据的情况下,XYZ算法平均速度最快,正如Smith等人[1]所证实的那样” . 但欢迎任何其他信息 .
Note :我会将赏金奖励给得票最高的答案 . 明智地投票!
7 回答
如果您正在排序的数据具有已知分布,我将使用 Bucket Sort 算法 . 您可以为它添加一些额外的逻辑,以便您根据分布的属性计算各种桶的大小和/或位置(例如:对于Gaussian,您可能每个(sigma / k)远离均值,其中sigma是分布的标准偏差) .
通过以这种方式获得已知的分布并修改标准的Bucket Sort算法,您可能会获得 Histogram Sort 算法或与其接近的算法 . 当然,您的算法在计算上会比直方图排序算法快,因为您可能不需要进行第一次传递(在链接中描述),因为您已经知道了分布 .
Edit: 给出了您的问题的新标准,(虽然我以前的答案有关直方图排序链接到可敬的NIST并包含性能信息),这是来自国际并行处理 Session 的同行评审期刊文章:
Adaptive Data Partition for Sorting Using Probability Distribution
作者声称这种算法比流行的快速排序算法具有更好的性能(高达30%) .
听起来你可能想要阅读Self-Improving Algorithms:它们实现了任意输入分布的最终预期运行时间 .
如果你已经知道你的输入分布大致是高斯分布,那么在空间复杂度方面可能另一种方法会更有效,但就预期的运行时间而言,这是一个相当奇妙的结果 .
知道了数据源分布,就可以构建一个好的哈希函数 . 很好地了解分布,散列函数可以证明是完美的散列函数,或者对于许多输入向量来说接近完美 .
这样的函数将大小为n的输入分成n个区间,使得最小的项目将映射到第一个区域,并且最大的项目将映射到最后的区域 . 当哈希是完美的 - 我们将实现排序只是将所有项目插入到箱子中 .
将所有项插入哈希表,然后按顺序提取它们将是哈希完美时的O(n)(假设哈希函数计算成本为O(1),并且下划线哈希数据结构操作为O(1) ) .
我会使用一组斐波那契堆来实现哈希表 .
对于哈希函数不完美(但仍然接近完美)的输入向量,它仍然比O(nlogn)好得多 . 当它是完美的 - 它将是O(n) . 我不确定如何计算平均复杂度,但如果被迫,我会打赌O(nloglogn) .
计算机排序算法可以分为两类,基于比较的排序和基于非比较的排序 . 对于基于比较的排序,其中的排序时间最佳情况是Ω(nlogn),而在最坏情况下,性能排序时间可以上升到O(n2) . 近年来,已经提出了一些改进的算法来加速基于比较的排序,例如根据数据分布特征的高级快速排序 . 但是,这些算法的平均排序时间仅为Ω(nlog2n),只有在最佳情况下才能达到O(n) . 与基于比较的排序不同,基于非比较的排序(例如计数排序,桶排序和基数排序)主要取决于密钥和地址计算 . 当密钥的值在1到m的范围内是有限的时,非基于比较的排序的计算复杂度是O(m n) . 特别是,当m = O(n)时,分选时间可以达到O(n) . 然而,当m = n2,n3,...时,不能获得线性分类时间的上限 . 在基于非比较的排序中,桶排序将具有相似密钥的一组记录分配到适当的“桶”中,然后将另一排序算法应用于每个桶中的记录 . 使用存储桶排序,将记录划分为m个桶的时间较少,而每个存储桶中只包含少量记录,因此可以非常快速地应用“清理排序”算法 . 因此,与Ω(nlogn)算法相比,桶分类有可能渐近地节省排序时间 . 显然,如何将所有记录均匀地分配到桶中在桶分类中起着关键作用 . 因此,您需要一种根据数据分布构造哈希函数的方法,该方法用于根据每条记录的密钥将n条记录均匀分布到n个桶中 . 因此,在任何情况下,所提出的桶分类算法的分类时间将达到O(n) .
查看本文:http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5170434&tag=1
只要您可以在O(1)时间内计算每个点的CDF,Bucket sort就会为您提供线性时间排序算法 .
您也可以在其他地方查找的算法如下:
运行时间是期望的O(n)因为期望有O(n)对(x,y)使得x和y落在同一个桶中,并且插入排序的运行时间恰好是O(n#对)在同一桶) . 分析类似于FKS static perfect hashing .
编辑:如果你不知道分布,但你知道它是什么样的家族,你可以通过计算均值和方差来估计O(n)中的分布,在高斯情况下,然后使用相同的算法(顺便说一下) ,在这种情况下计算cdf是非常重要的) .
您可以在快速排序中使用该信息来选择透视值 . 我认为这将提高算法远离O(N ** 2)最坏情况复杂度的概率 .
我认为cycle sort属于这一类 . 当您知道希望每个元素最终到达的确切位置时,可以使用它 .