问题标签 [timsort]

块上有一个（相对）新的排序，称为 Timsort。它被用作 Python 的 list.sort，现在将成为Java 7 中的新 Array.sort。

有一些文档和一篇很小的 Wikipedia 文章描述了排序的高级属性和一些低级性能评估，但我很好奇是否有人可以提供一些伪代码来说明 Timsort 到底在做什么，以及关键的事情是什么这使它变得活泼。（特别是关于被引用的论文，“乐观排序和信息论复杂性”。）

（另请参阅相关的 StackOverflow 帖子。）

对平滑二维数组中的值进行排序的最快方法是什么？

输入是一个小的过滤图像：

• 约 60 x 80 像素
• 单通道
• 单精度或双精度浮点数
• 行主要存储，在内存中顺序
• 值有混合符号
• 分段“平滑”，区域宽度约为 10 像素

输出是已排序值的平面（大约 4800 个值）数组，以及对原始数组进行排序的索引。

我找不到Java 7的文档，我只能找到关于Java 6的，它仍然是快速或合并的。有谁知道如何Arrays.sort在 Java 7 中找到该方法的文档？

TimSort 是一种在 Java 7 中默认用于排序的算法。

我找到了这个来源，但我不明白要调用哪个方法，因为它们都是私有的。有人能理解吗？谢谢你。

http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java

为什么当 Timsort（根据维基百科）似乎表现得更好时，我大多听说 Quicksort 是最快的整体排序算法？谷歌似乎没有进行任何比较。

我想根据我的一些想法开发一种非常有效的排序算法。问题是我想针对已经存在的大多数高度赞赏的排序算法来测试我的算法的效率。

理想情况下，我想找到：

• 一大堆排序测试对于为我提供算法的效率非常重要
• 大量已经存在且经过高度优化的排序算法（带有它们的代码 - 无论是哪种语言）
• 更好的是，为排序算法开发人员提供足够环境的软件

这是我之前发现的一篇文章，其中包含 2 个表，比较了 timsort、quicksort、dual-pivot quicksort 和 java 6 sort：http ://blog.quibb.org/2009/10/sorting-algorithm-shootout/ 我可以看到在那些TXT文件（从1245.repeat.1000.txt到sequential.10000000.txt）包含这些算法的测试用例的表格中，但我在任何地方都找不到原始TXT！

谁能指出我与许多排序测试用例和/或许多高效排序算法的任何链接？（这是我最感兴趣的测试用例，排序算法遍布互联网）

非常感谢您！

我挑战自己在 Common Lisp 的算法课上完成所有作业。我进入学习 lisp 的第一天，但​​遇到了障碍。

任务是创建一个合并排序，当您达到任意子集长度时转换为插入（Timsort）。插入部分完美运行，但合并的拆分部分仅在程序必须拆分两次时才有效。我知道这与列表在 lisp 中的工作方式有关，我太新了，无法查明问题。

我认为它要么遇到无限循环......我不确定，因为当我使用调试语句运行它时，当集合中有太多元素时它们永远不会被打印出来。

我不是在这里乞求具体的答案或有人写我的代码。也许一个解释或一个正确方向的观点会有很大帮助！

我的代码：

注意：这是我写的代码，不是从互联网上下载的......你可能会知道哈哈

我正在研究“timsort”算法对我相当大的数据集进行一些排序：http: //timsort4net.codeplex.com/

通常我使用Array.Sort(Keys, Items)where Items 是一个整数数组，用作识别排序期间发生的位置变化的方法。

有没有办法在不必大量修改排序算法的实现的情况下获得同样的结果？

我正在尝试理解 Timsort 算法，但是由于实现堆栈不变量的原因，我遇到了麻烦：

1. A > B+C
2. B > C

根据这份文件，

我们希望尽可能长时间地延迟合并，以便利用以后可能出现的模式，但我们更希望尽快进行合并，以利用刚刚找到的运行在内存层次结构中仍然很高。

我知道我们希望尽快进行合并以利用缓存效应，但我不明白我们为什么要延迟它的原因。他所说的“模式”是什么意思？

我发现了 Timsort 的 Swenson 的 C 实现： https ://github.com/swenson/sort在较早的 SO 问题之一中提到。

我遇到了两个问题：

1）要使用它，我需要定义适合我想要排序的类型的 SORT_CMP 宏。我的类型被定义为（这里有点简化）：

我尝试定义：

但我不断收到一个错误：“在不是结构或联合的东西中请求成员'a'”我认为也许 x 和 y 将是指针，但是：

也不行。你能帮我解决这个问题吗？我是 C 新手，可能缺少一些基本的东西。

2）有没有办法在 Visual Studio 中编译该代码？它使用来自较新的 C 标准的东西（比如块中间的声明）并且 cl.exe 不接受它。我使用 GCC (mingw) 编译它，但 mingw 的其余代码比 VC 慢 20%（使用 O2 或 O3 标志 vs lc.exe 使用 /Ox）所以我可以从使用 Timsort 而不是 stdlib qsort 中获得任何收益不会弥补的。Pelles 编译器也是如此。我的大部分数据都有很多部分排序的序列，排序需要大约 50% 的执行时间，所以我觉得假设我让它在 VC 中工作，这里有收获。