问题标签 [timsort]

我一直在谷歌上搜索并阅读维基百科上的 Timsort 和其他资源。然而，我对 Timsort 在做什么并没有明确的想法。任何人都可以描述该算法，或者向我提供一些包含清晰描述的文档吗？

我想知道 PHP 中是否有任何算法与 Python 中实现的用于排序列表的 timsort 算法等效？

碰巧我不得不将一些代码从 python 翻译成 php。

我正在使用的数据集的一些特征显示出以下趋势：-

1. 数组的前 50-70% 几乎已排序，最后 30% 完全打乱。

   • 如果我将插入排序部分替换为shell排序会有效吗？
     

2. 数组的前 50-70% 几乎已排序，最后 30% 包含很多海龟。

   • 海龟的出现是否如此重要，以至于我应该放弃 Timsort 以支持这种 Comb 排序变体 - 在这里。他们的最佳案例性能显示 O(n)，但平均案例性能对于使用 O(n log n) 的 Tim 排序更好，而 Comb 排序有 Ω (n log n) 但这是否需要修改版本的 Comb 排序或海龟密度考虑到？
     

3. 与第二种情况相同，但如果可以提高性能，部分排序的输出就可以了。例如，一个包含 1,000,000 个元素的数组可以在数组的前 1% 个槽中拥有其最小的 1%（即 10,000 个元素），但不需要在内部进行排序。

   • 这可以通过在快速排序中的某个递归深度后拉出以将元素大致放置在它们应得的位置附近来完成。

如果相关，这里是我正在尝试修改的 Java 的 Timsort 代码 -代码。

我制作了一个带有 jPanel 和 JLabel 数组的调色板。起初它运行良好，但后来我将其他一些 jLabels 从 JPanel 中取出并添加了一些事件。现在我不断收到此错误：

在我第一次收到此错误后，我试图删除我所做的所有事情，但仍然会收到它。当我将布局从 GridLayout 更改为其他任何内容时，错误就会消失，但代码变得无用。所以我需要GridLayout。当我将该 JPanel 中的所有内容移动到另一个 JPanel 时，错误也会消失。但是当我删除第一个 JPanel 时，错误又回来了。

顺便说一句，该程序可以运行，但是不断出现错误并不令人高兴...

编辑：当我使用少于 225 的颜色时，没有错误。我真的很好奇发生了什么。任何解释将不胜感激......

从维基百科上阅读这篇关于排序算法的文章，smoothsort 似乎是最好的排序算法。它在所有类别中都具有最佳性能：最佳、平均和最差。在任何类别中都没有什么能比得上它。它还具有恒定的内存要求。唯一的缺点是不稳定。

它在内存方面胜过 timsort，在最坏情况下的性能和内存方面都胜过 quicksort。

但我从来没有听说过smoothsort。没有人提到它，而且大多数讨论似乎都围绕着其他排序算法。

这是为什么？

如何以 Javascript 格式使用 Timsort？Java、Python 和 C++ 中有很多文档，在 JS 中也可以使用吗？

我们最近在从 Java 6 迁移到 7 时遇到了一些麻烦，因为我们有大量的 Comparator 以一种无法满足 Comparable 合约并使用新的 Timsort 算法抛出异常的方式实现。

编辑：来自用户 Marco Forberg 的输入和类签名

我现在发现了一个 Comparator 许多其他的扩展，比较方法看起来像这样：

我把它改成了这个，希望能涵盖大多数情况：

类签名如下所示：

WhileObjectUtils来自 Apache Commons 3 并提供了一个 null 安全的比较方法（我知道我调用它的时候，由于之前的检查，两个对象都不能为 null，我也可以使用 c1.compare(c2) ）

这是否改善了“基础”比较器的行为？（我假设）我是对的，这基本上涵盖了 Comparable 合同，因为现在为不可比较的对象返回值 0？

来自：

http://svn.python.org/projects/python/trunk/Objects/listsort.txt

和：

http://en.wikipedia.org/wiki/Timsort

我明白了，Timsort 有一些优化 when a0 > a1 > a2 > ...，但是下一个数组呢：

10000,10000,9999,9999,9998,9998,....,9,9,8,8,7,7,6,6,5,5,4,4,3,3,2,2,1,1,0,0

这种阵列的时间效率是多少？

（整数用于简化示例，需要稳定的排序）我已经进行了一些测量，似乎这样的数组对于 Timsort 来说不是“好”的情况。

实际上，JDK http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java 中的 TimSort 有一个方法“countRunAndMakeAscending”

为什么不以另一种方式实现它：

所以它会在非升序下正常工作吗？

我听说 Timsort 在某些情况下利用数据模式打破了 O(n log n) 界限。怎么可能？谁能详细解释我？如果这是真的，那么 Timsort 将总是比快速排序进行更少的比较，因为在现实生活中的数据中存在一些模式，除了数据是真正随机的？

我们可以使用某种技巧来打破 O(n log n) 限制在 avg 情况下进行比较排序吗？

我发现了一种更有效的排序算法，平均和最佳性能为 O(N)，最差性能为 O(N Log(N))。关于均匀分布的数据。

我需要你的帮助来告诉我我的测试是否正确，而我最大的问题是：如何在真实世界的数据上进行测试？

这个问题将有五个部分：

• 关于 java.util.Collections.sort 的简短介绍
• 关于我的算法的解释
• 测试输出
• 我的算法的源代码
• 我的测试程序的源代码

关于 java.util.Collections.sort 的简短介绍

Java在Collections.sort实现中使用改进的合并排序算法。从 jdk 7 开始，它被替换为timsort。在我的测试中，我一直在使用 jdk 6。与 Android 中使用的相同。

关于我的算法的解释

我发现了一种有趣的排序方法。我使用统计排序。或者更准确地说是线性统计排序。我假设所有变量都有“好的”线性回归。因此，我正在根据变量的值计算变量的近似索引。如果多个变量具有相同的索引，我将它放在缓冲区数组中。比我使用 Collections.sort() 对缓冲区进行排序。这个想法是缓冲区将非常小，因此对其进行排序将是〜O（1）。这是 O(N) 和 O(N Log(N)) 性能之间的差异，在最坏的情况下它的大小是 N。之后我在我的近似排序数组和缓冲区之间进行合并。结果是排序数组。

测试输出

• 我的时间/系统时间 = 511 / 859 = 0.5948777648428405
• 我的时间/系统时间 = 417 / 467 = 0.892933618843683
• 我的时间/系统时间 = 309 / 403 = 0.7667493796526055
• 我的时间/系统时间 = 308 / 344 = 0.8953488372093024
• 我的时间/系统时间 = 204 / 483 = 0.422360248447205
• 我的时间/系统时间 = 204 / 368 = 0.5543478260869565
• 我的时间/系统时间 = 279 / 291 = 0.9587628865979382
• 我的时间/系统时间 = 206 / 288 = 0.7152777777777778

我的算法的源代码

我的测试程序的源代码

性能测试

主要的