维护或衡量集合排序的最佳方法是什么,以便我们可以选择最佳排序算法?

扩充@doug:

删除永远不能成为列表 较少的 排序,所以你不必跟踪它们。

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

也许这是一个太多的惩罚(即每插入两个比较)。你只能做一个比较来得到更模糊的结果?或者我真的很喜欢只是数插页的想法。

您可以使用采样:检查列表中均匀分布的n个元素,看看有多少元素是有序的。(当然,这只适用于随机访问列表,但通常是您排序的类型。)

如果n很小(例如 10 )即使列表未排序,插入排序也很好。Java对小N进行了优化,否则是合并排序。

一种支撑溶液:

维护上次排序后执行的操作(插入/删除)数。这个数字越高,这个集合可能就越不排序。

你可以测量数据的频率——如果每一项都有很大的变化,那么数据就是高频率的,这表明数据分布是相当随机的。

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

你也可以用一个过滤器来测量总体趋势——是可以向下或向上测量的平均趋势——如果向下,你可以考虑翻转整个数组,或者使用一种适合“反转”数据的排序方法。

还有其他的测量方法,你可以使用可能给你的洞察力-检查信号处理,看看你能收集到什么。

-亚当

有一种内省的方式能做到这一点,有点…

http://ralphunden.net/content/tutorials/a-guide-to-introsort/

如果你什么都不知道 先验的 关于收集,任何时间花在仪器它的分类将远远大于节省你会得到选择的最佳排序算法。

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

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

如果试图扩展集合类以跟踪排序,只需保留指向集合中元素的指针的单独排序列表…

最后,99.99%的时间,为什么要费心?使用快速排序。如果您的数据集足够小,以至于QuickSort上大O排序的常量部分将覆盖气泡排序的时间节省,则排序速度将非常快,您甚至不应该浪费时间提出问题。

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

这是个很好的问题。我解决这个问题的方法是:给定一个项目列表,从列表中选择两个已排序的连续项目的概率是多少?当列表变得更加有序时,概率将接近100%。

计算这种概率相对简单:

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

我希望这有帮助!