algorithm - 最小化涉及单个项目的最大比较次数的排序算法

Question

我有兴趣找到一种比较排序算法，该算法可以最大限度地减少算法运行期间每个元素与其他元素进行比较的次数。

对于随机排序的列表，我对两个分布感兴趣:对列表进行排序所需的比较次数(这是传统标准)和涉及列表中每个单个元素的比较次数.

在比较次数方面表现良好的算法中，比如说平均达到 O(n log(n))，我想找出平均次数为 O(n log(n)) 的算法单个元素与其他元素相比被最小化。

我假设理论上的最小值是 O(log(n))，它是将上图的总比较次数除以 n 得到的。

我也对数据可能已经在某种程度上被订购的情况感兴趣。

也许模拟是寻找答案的最佳方式？

(我之前的问题搁置了 - 现在这个问题很清楚了，如果你不明白请解释原因)

Answer 1

是的，您绝对应该进行模拟。
在那里，您将以一种允许比您提出的一般问题更具体的陈述的方式隐含地设置大小和预排序约束。

但是，一般来说，可能无法明确回答此类问题。

Big-O 在您提出问题时处理渐近行为似乎针对较小的问题规模。因此 Big-O 可以暗示用于排序运行的足够大的输入集的最佳候选者。 (但是，例如，如果您对 size<=5 感兴趣，结果可能会完全不同!)为了获得对比较操作的正确估计，您需要分析每个单独的算法。

最后，结果(对于给定的算法)将必须特定于正在排序的数据集。

此外，on avarage 在您的上下文中没有明确定义。我假设您打算引用给定排序的参与对象的比较次数，而不是对一组(足够大的)排序运行的平均数。

即使在单一算法中，单个对象的比较分布在一种情况下可能显示出较大的标准偏差，而在另一种情况下(几乎)均匀分布。

由于排序算法的复杂性由比较总数(及其位置变化)决定，我认为理论分析不会对答案有多大贡献。

也许您可以添加一些背景知识，说明什么会使您的问题的答案在实际意义上“有趣”？