我很想找到一种比较排序算法，该算法可以最大限度地减少在算法运行期间每个元素与其他元素进行比较的次数。排序算法最大限度地减少了涉及单个项目的最大比较次数
对于随机排序的列表，我对两个分布感兴趣：对列表进行排序所需的比较次数（这是传统标准）以及列表中每个单个元素的比较次数参与其中。
在比较数量方面表现出色的算法中，比如平均实现O（n log（n）），我想找出一个平均值为单个元素与其他元素进行比较的次数被最小化。
我认为理论上的最小值是O（log（n）），它是通过将上图中的比较总数除以n得到的。
我对数据可能已经在一定程度上已经订购的情况也感兴趣。
也许模拟是寻找答案的最佳方式？
（我以前的问题一直被搁置 - 现在这是一个非常明显的问题，如果你不能了解它，然后请解释原因）
是你绝对应该做的模拟。
在那里，你会隐式设置大小和预约约束的方式，可能允许比你提出的一般问题更具体的语句。
还有可以，但是，一般来说这不是一个明确的答案。
Big-O处理渐近行为，而您的问题 似乎针对较小的问题大小。所以Big-O可以暗示最好的候选人有足够大的输入集来进行排序。 （但是，例如，如果您对尺寸< = 5感兴趣，结果可能会完全不同！） 为了获得对比较操作的正确估计，您需要 来分析每个单独的算法。
最后，结果（对于给定的算法）必须特定于要排序的数据集。
另外，on avarage在您的上下文中没有很好定义。我假设你打算参考给定排序的参与对象的比较次数，而不是一个（足够大）的排序集合上的avarage。
即使在单个算法中，单个对象发生的比较分布也可能在一种情况下显示较大的标准偏差，在另一种情况下可能（几乎）均匀分布。
由于排序算法的复杂性是由比较的总数（及其位置变化）决定的，所以我不认为从理论上分析会有助于答案。
也许你可以添加一些背景知道什么可以使你的问题的答案在实际意义上“有趣”？
程序员stackexchange可能是这个问题的一个更好的地方，请参阅：http：//programmers.stackexchange。com/help/on-topic – nibarius
@rpy：平均而言，我是指长度为n的列表的预期数量，假设所有初始订单具有相同的可能性。对于一个具体的例子，你可能想要考虑使用一种算法来提供比较，而真正的人进行比较（例如，图片/想法之间）;在这种情况下，目标是尽可能减少冗长的比较。 – Gio
@nibarius在提及其他网站时，指出[交叉发布令人不悦]（http://meta.stackexchange.com/tags/cross-posting/info） – gnat