已知统计分布数据的排序算法？

Question

刚才我想到，如果您对要分类的数据的分布（从统计角度来说）有所了解，那么如果将这些信息考虑在内，排序算法的性能可能会受益。

所以我的问题是，有任何排序算法考虑到这种信息？他们有多好？

编辑：一个例子来说明：如果您知道数据的分布是高斯分布，那么您可以在处理数据时快速估计均值和平均值。这会给你估计每个数字的最终位置，你可以使用它们将它们放在最接近他们的最终位置。

编辑＃2：我很惊讶，答案并不是维基链接到讨论这个问题的讨论页面。这不是一个很常见的情况（例如高斯情况）？

编辑＃3：我给这个问题增加了一个赏金，因为我在寻找有确切答案的来源，而不是猜测。就像“在高斯分布式数据的情况下，XYZ算法是平均速度最快的，正如Smith等[1]所证实的那样”。但是，欢迎任何其他信息。

注意：我会奖励赏金答案最高的答案。明智地投票！

Answer 1

如果您正在排序的数据具有已知分布，我将使用Bucket Sort算法。您可以添加一些额外的逻辑，以便根据分布的属性计算各个桶的大小和/或位置（例如：对于高斯，您可能每隔（σ/ k）距离均值就有一个桶，其中西格玛是分布的标准偏差）。

通过以这种方式进行已知分配并修改标准桶排序算法，您可能会得到算法或其他相近的算法。当然，你的算法在计算上比直方图排序算法快，因为你可能不需要做第一遍（在链接中描述），因为你已经知道分布。

编辑：你的问题的给您的新标准，（虽然我以前关于直方图排序链接到可敬NIST和包含的性能信息的答案），这里是从并行处理国际会议进行同行评审期刊文章：

Adaptive Data Partition for Sorting Using Probability Distribution

作者声称该算法具有更好的性能（更好的高达30％），比流行的快速排序算法。

Answer 2

了解数据源分布，可以构建一个好的散列函数。很好地了解分布，哈希函数可能被证明是一个完美的散列函数，或者接近完美的许多输入向量。

这样的函数会将大小为n的输入分成n个bin，这样最小的项目将映射到第1个bin中，最大的项目将映射到最后一个bin。当散列是完美的 - 我们将实现排序只是将所有项目插入箱。

将所有项目插入散列表中，然后按照顺序提取它们将是O（n），当散列是完美的时（假设散列函数计算成本是O（1），并且下划线散列数据结构操作是O（1））。

我会使用斐波那契堆数组来实现哈希表。

对于散列函数不完美（但仍然接近完美）的输入向量，它仍然会比O（nlogn）好得多。当它完美时 - 它会是O（n）。我不知道如何计算平均复杂度，但如果被迫，我会在O（nloglogn）上下注。

Answer 3

您可以在快速排序中使用该信息来选择枢轴值。我认为这会提高算法避免O（N ** 2）最差情况复杂度的可能性。

Answer 4

听起来像你可能想要读Self-Improving Algorithms：它们实现了任意输入分布的最终最佳期望运行时间。

我们得到这样的自改进算法 为两个问题：（ⅰ）排序号码 序列和（ii）计算 平面 点集的Delaunay三角剖分。两种算法均实现最佳期望限制复杂度。该算法开始于训练 阶段，在该阶段期间，他们收集关于输入 分布的信息，随后是固定的 机制，其中算法将 设置为其优化的化身。

如果您已经知道您的输入分布近似为高斯，那么也许另一种方法在空间复杂性方面会更高效，但就预期运行时间而言，这是一个相当不错的结果。

Answer 5

计算机排序算法可以分为 两类，基于比较的排序和非基于比较的排序 。对于基于比较的 排序，其最佳情况下的排序时间为 Ω（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

Answer 6

桶排序会给你一个线性时间排序算法，只要你可以计算在O（1）每一个时间点的CDF。

的算法，你也可以看看在其他地方，如下：

a = array(0, n - 1, [])   // create an empty list for each bucket 
for x in input: 
    a[floor(n * cdf(x))].append(x) // O(1) time for each x 
input.clear() 
for i in {0,...,n - 1}: 
    // this sorting step costs O(|a[i]|^2) time for each bucket 
    // but most buckets are small and the cost is O(1) per bucket in expectation 
    insertion_sort(a[i]) 
    input.concatenate(a[i]) 

的运行时间是在预期为O（n），因为在预期有O（N）对（X，Y ），使得x和y落入同一个桶中，并且插入排序的运行时间恰好是O（n +＃在同一个桶中）。该分析类似于FKS static perfect hashing。编辑：如果你不知道分布，但你知道它来自哪个家族，你可以通过计算均值和方差来估计O（n）中的分布，在高斯情况下，然后使用相同的算法（顺便说一下，在这种情况下计算cdf是非平凡的）。

Answer 7

我认为cycle sort属于这一类。当你知道每个元素最终的确切位置时，就可以使用它。

Cyclesort有一些很好的属性 - 对于某些限制类型的数据，它可以在线性时间内进行稳定的就地排序，同时保证每个元素最多只能移动一次。