我想知道稳定排序会产生巨大影响的场景。

以前版本的 JAVA 对 collections.sor API 进行了合并排序，这是一种稳定的排序，而对于 Array.sort，使用了快速排序。当前版本的 Java 使用 Tim 排序，这又是一种稳定的排序。所以现在如果你会看到大多数流行的语言，如 Python、Java、Scala 都在使用 Tim Sort。我想知道 Tim Sort 在使用中稳定排序的重要性。推动使用稳定分拣技术的强大动机是什么？

这是一个问题，是什么是识别列表中连续重复项的最 Pythonic 方式的扩展？.

假设您有一个元组列表：

然后按每个元组的最后一个值对其进行排序：

然后我们有两个连续的运行（查看每个元组中的最后一个值），即[(3,2), (5,2)]和[(1,4), (4,4)]。

反转每次运行的pythonic方式是什么（不是里面的元组），例如

这可以在发电机内完成吗？

更新

我注意到示例列表可能不清楚。因此，请考虑：

理想的输出来自reverse_runs哪里

为了明确术语，我采用了“运行”来描述TimSortPython 的排序函数所基于的内容——赋予它（排序函数）它的安全性。

因此，如果您对集合进行排序，如果集合是多面的，则仅对指定的维度进行排序，如果指定维度的两个元素相同，则它们的排序将不会改变。

因此以下功能：

产量：

"C"并且（即）上的运行(5, 'C'), (4, 'C'), (3, 'C')不受干扰。

所以总而言之，来自尚未定义的函数的期望输出reverse_runs：

1.) 按元组的最后一个元素对元组进行排序

2.) 保持第一个元素的顺序，在最后一个元素上反向运行

理想情况下，我希望在生成器函数中使用它，但这（目前对我来说）似乎是不可能的。

因此，可以采用以下策略：

1.）通过最后一个元素对元组进行排序sorted(my_list, key=lambda tuple: tuple[1])

2.) 当后续元组 (i+1) 与 (i) 中的最后一个元素不同时，识别每个元组中最后一个元素的索引。即识别运行

3.）制作一个空列表

4.) 使用拼接运算符，获取、反转并将每个子列表附加到空列表

编辑：部分解决。按照第一个答案的建议，我将 NULL 检查切换为 while 循环检查中的第一个，但是我仍然无法访问队列中的任何元素，除了第一个元素。我可以访问 data->head，但我无法访问 data->head->next，除非我专门创建了一个指向 data->head->next 的节点结构。如果我专门创建了那个节点（我们称之为 temp），那么 temp->next 也是不可访问的。基本上，当我将队列传递给这个函数时，->next 功能完全丢失了，我不知道为什么。

我正在为 Uni 开展一个学校项目，在该项目中我们构建了一个修改过的归并排序（编辑：一位评论者指出这是 TimSort 的一种形式），它不是普通的归并排序算法，而是将数据集划分为已经排序的数据块，并且然后重新组合它们以理论上减少运行时间。
作为一个例子与集合

会被分成

然后按排序顺序重新合并在一起。我们的特定实现必须使用链表、队列和堆栈来完成。
这是我的链表定义和队列定义：

我遇到问题的代码在识别“运行”的函数中，或者数据已经排序的数据区域。它将队列作为输入，遍历并识别第一个节点是否小于或大于下一个节点。然后它选择要运行的循环并将每个值出列到新队列中，然后将作为“运行”返回，这是已排序数据的子集。
出于某种原因，每当我尝试使用 data->head->next 或 data->head->next->value 时，它​​都会引发分段错误，即使我知道节点存在并且值存在。我一直在通过 gdb 运行我的程序来查找错误点，我在 Windows 上，我不能使用 valgrind。这是我遇到问题的函数的代码：

以下是让我难以理解的原因：

让我烦恼的另一件事是我能够在其他函数中使用 queue->head = queue->head->next 并且工作正常，我可以使用 node = node->next 并且工作正常，所以我真的不知道问题是什么。我知道这个函数中调用的函数可以工作，但我很乐意为它们提供代码。这里有声明，如果需要，我可以提供我的所有代码（不想让这个问题太长）：

任何帮助将不胜感激，我一直在试图找出问题所在，但到目前为止我还没有成功。提前致谢！

我刚刚编写了一个测试程序来违反使用 Tim Sort 的 Java 7 的 compareTo 方法中的传递性。下面是我比较的实现。

正如预期的那样，当我尝试运行程序时它会引发以下异常，因为它违反了传递性 -

检查零（对于整数）或空（对于字符串或任何其他对象）值并仅在两个元素不为零或不为空时才比较这两个元素而不会出现 Tim Sort 异常的最佳方法是什么？我怎样才能编写上面的代码，这样我就不会得到错误，而只比较非零整数？

我搜索并找不到 TimSort 在哪个版本中实际替换了 collections.sort() 方法中的 MergeSort。如果有人可以让我知道 JDK7 的确切版本，那将是一个很大的帮助。

我对 Python 相当陌生，正在尝试编写一个 timsort 重新实现。在编写程序时，我无法弄清楚如何获得最小运行长度。我咨询过的消息来源将 minrun 描述为：

minrun = N/minrun<=2^N 其中 n 是数组的大小。

我明白我想要做什么，我只是不知道如何在 Python 中做到这一点？

任何想法或示例代码都会非常有用，谢谢！

这是一个非常接近我要在我的项目中实现的代码片段：https ://repl.it/@Twinbird24/TimSort-example

这是我正在使用的包：https ://www.npmjs.com/package/timsort

我试图通过每个对象的名称属性对我的对象数组进行排序，该属性包含一个字符串——尽管我的函数也可以传递另一个项目来排序（即“年龄”）。

TimSort 的文档不是很清楚，通过查看源代码我仍然不太能够弄清楚如何配置我的代码。

您会在我的代码中注意到，我还想选择按“升序”或“降序”进行排序，但我不确定如何将其添加到我正在使用的 TimSort 方法中。

我试图理解 timsort 算法。维基百科说合并使用几乎就地策略，在合并排序之前运行受限于二进制搜索以优化性能。

Timsort 执行几乎就地合并排序，因为实际的就地合并排序实现具有很高的开销。First Timsort 执行二分查找，以查找第二次运行中第一个元素在第一次运行中的位置，以及第一次运行中最后一个元素在第二次运行中的位置。这些位置之前和之后的元素已经在其正确的位置，并且可以从进一步考虑中删除。

然后，关于驰骋模式，说明如下

上面的单独合并保留了从同一输入集中选择的连续元素的计数。当达到最小疾驰阈值 (min_gallop) 时，算法切换到疾驰模式。这试图利用数据中的子运行；因此，舞动的成功或失败用于调整最小舞动阈值，作为数据是否包含足够的子运行的指示。（初始阈值为 MIN_GALLOP。）[6]

选择的输入集让我想到了二分搜索优化后的运行结果。但它也说

此外，在发现疾驰比二分搜索效率低的情况下，退出疾驰模式。

这给了我相反的印象，即驰骋可以替代二分搜索优化。

那么，用于合并的二分搜索优化是奔腾补充还是替代？有人可以给我更清楚地解释整个算法（尤其是合并和驰骋模式），因为我在一般算法领域相对较新。

为什么 Java 的Tim Sort 实现是顺序的？发现和合并运行可以同时进行。

来自维基百科：

Timsort 旨在利用大多数真实世界数据中已经存在的连续有序元素的运行，自然运行。它将数据收集元素迭代到运行中，并同时将这些运行合并在一起。

编辑：Java 9 中的 TimSort 实现仍然是顺序的。

使用 Java 8 u151

我们正在进行以下排序：

其中 getValidStartTime 和 getValidEndTime 是 Date 对象。

显然这段代码是错误的，因为我们的目标实际上只是根据开始时间进行排序。

然而，不幸的是，导致问题的数据已从数据库中删除，我们得到了臭名昭著的 IllegalArgumentException。这似乎是合乎逻辑的，因为在元素之间，我们没有使用相同的值进行比较（A.start 与 B.end 进行比较，但 B.start 与 C.end 进行比较）。

我不能做的是找出导致再次引发此异常的数据集。修复代码以始终比较开始时间是正确的方法，但在数据集之前和之后的测试方面，我无法展示修复的证据（尽管每个人都已经同意我们正在进行更改）。

尝试查看抛出此问题的 TimSort 的 mergeHi 方法，但我不能完全了解所有的疾驰和数组复制内容。所以虽然我可以知道异常是在哪里抛出的，但让它可重现却失败了。

Date 对象在排序之间是静态的。一旦在数据库中设置，它们就是不可变的。列表本身在排序过程中也没有改变。所以对我来说，我可能是错的，这指向数据，并且我们有一些奇怪的开始和结束日期组合违反了传递子句，但我尝试过的每个组合总是有一个有效的（如果不是有点奇怪的话看）排序。

谢谢！