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

Question

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

score 3 · Accepted Answer

增强@Doug：

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

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

也许这是太多的惩罚（即每个插入两次比较）。你可以只做一个比较以获得更模糊的结果吗？或者我确实喜欢只计算插入的想法。

score 2 · Accepted Answer

有内省排序正是这样做的，有点......

score 2 · Accepted Answer

您可以使用抽样：检查列表中均匀分布的 N 个元素，看看有多少是按顺序排列的。（当然，这只适用于随机访问列表，但通常这是您排序的类型。）

也有一个小 N 的阈值。如果 N 很小（例如10），即使列表没有排序，插入排序也是好的。Java 在合并排序中对小 N 进行了优化。

score 2 · Accepted Answer

一种建议的解决方案：

保持自上次排序以来执行的操作（插入/删除）的数量。这个数字越高，集合可能越未排序。

score 2 · Accepted Answer

您可以测量数据的频率——如果从一个项目到另一个项目有很多大的变化，那么数据是高频率的，表明一个相当随机的分布。

如果变化较小，则数据频率较低 - 表示非随机分布。

您还可以使用过滤器测量总体趋势 - 是可测量的向下或向上的平均趋势 - 如果向下，您可能会考虑翻转整个数组或对“反转”数据使用良好的排序。

您可以使用其他测量方法，可能会给您带来洞察力 - 检查信号处理，看看您能收集到什么。

-亚当

score 1 · Accepted Answer

如果您对集合一无所知，那么尝试检测其排序性所花费的任何时间都将远远超过选择最佳排序算法所节省的时间。

另一方面，如果您要对许多具有相似排序量的数据集进行排序，则可以测量第一个数据集，选择一种算法，然后将其用于所有后续数据集。

score 0 · Accepted Answer

好吧，首先检查集合是否按定义排序，这将始终为您节省大量时间 :) 在大多数情况下，不要费心扩展集合来测试它是否在其插入/删除操作期间排序，如果集合需要排序，使用按定义排序的集合。

如果您尝试扩展集合类以跟踪排序，只需保留一个单独的排序列表，其中包含指向集合中元素的指针......

最后，在 99.99% 的时间里，何必呢？只需使用快速排序。如果您的数据集足够小，以至于快速排序中 Big O 排序的常数部分将覆盖冒泡排序所节省的时间，那么排序将如此之快，您甚至不应该浪费时间问这个问题。

你真的告诉我你的问题是需要解决的排序的 0.01% 吗？

score 0 · Accepted Answer

这是一个很好的问题.. 我解决这个问题的方法是问：给定一个项目列表，从排序的列表中选择两个连续项目的可弹出性是什么。随着列表变得更加有序，概率将接近 100%。

计算这个概率比较简单：

int sorted = 0;
for (int i = 0; i < list_length; i++) {
    if (list[i+1] >= list[i]) {
       sorted++;
    }
}
sortedness = sorted/(list_length-1);

我希望这有帮助！

8 回答 8