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

Question

我突然想到，如果您对要排序的数据的分布(在统计意义上)有所了解，那么如果您将这些信息考虑在内，排序算法的性能可能会有所提高。

所以我的问题是，是否有考虑此类信息的排序算法？他们有多好？

需要说明的示例:如果您知道数据呈高斯分布，则可以在处理数据时即时估计均值和平均值。这将为您提供每个数字的最终位置的估计值，您可以使用它来将它们放置在靠近最终位置的位置。

我很惊讶答案不是指向讨论此问题的整页的 wiki 链接。这不是很常见的情况吗(例如高斯情况)？

我正在为这个问题添加赏金，因为我正在寻找具有来源的明确答案，而不是猜测。类似于“在高斯分布数据的情况下，XYZ 算法平均是最快的，正如 Smith 等人所证明的那样。[1]”。但是，欢迎提供任何其他信息。

Answer 1

如果您要排序的数据具有已知分布，我会使用 Bucket Sort 算法。您可以向其中添加一些额外的逻辑，以便根据分布的属性计算各种桶的大小和/或位置(例如:对于高斯分布，您可能每隔 (sigma/k) 远离均值就有一个桶，其中 sigma 是分布的标准差)。

通过已知分布并以这种方式修改标准桶排序算法，您可能会得到 Histogram Sort 算法或类似的东西。当然，您的算法在计算上会比直方图排序算法更快，因为您可能已经知道分布，因此可能不需要进行第一遍(在链接中描述)。

编辑:考虑到您的问题的新标准(虽然我之前关于直方图排序的回答链接到受人尊敬的 NIST 并包含性能信息)，这是来自国际 session 的同行评审期刊文章关于并行处理:

Adaptive Data Partition for Sorting Using Probability Distribution

作者声称该算法比流行的快速排序算法具有更好的性能(高出 30%)。