language-agnostic - 维护或衡量集合排序的最佳方法是什么，以便我们可以选择最佳排序算法？

Question

灵感来自 this question

如果我们提前知道集合的排序情况，则可以更好地选择使用哪种算法对集合进行排序。有没有一种方法可以衡量(或保持衡量)集合的排序情况？我们能否以这样一种方式来做到这一点，即维护或衡量某事物排序程度的成本不会超过选择最佳排序算法的好处？

Answer 1

增强@Doug:

删除永远不会减少列表的排序，因此您不必跟踪它们。

当插入发生时，与周围的元素进行比较以确定此插入是否有序。如果是，请不要增加计数器。如果不是，请增加“未排序”计数器。

也许这太过分了(即每个插入进行两次比较)。你只能做一个比较以获得更模糊的结果？或者我确实喜欢只计算插入次数的想法。