问题标签 [timsort]

假设我得到这些整数 6,1,4,2,1,5,9,6,3,4 并且运行的大小是 2 所以我们从每次运行的插入排序开始，我得到这些子数组：

1-6、2-4、1-5、6-9、3-4

我的问题是如何合并它们以获得排序数组？我的意思是我是否合并每两个数组，然后合并其余的等等？

我正在尝试在 Swift 中实现 TimSort。我已经提到了这两个链接：这个和这个 我已经转换为 Swift 的代码是：

我面临的问题是，当我在两个链接中执行代码时，它适用于任何运行值（如run = 7），但我的代码中没有发生同样的情况。

我的代码只有在run = 5和时才能正常工作arr.count = 10。arr.replaceSubrange(x..<min((x + 2 * runCount),(arr.count)), with: merge(leftPile: Array(arr[x..<(x + runCount)]), rightPile: Array(arr[(x + runCount)..<min((x + 2 * runCount),(arr.count))])))在所有其他情况下，它会在这条线上崩溃。

我尝试了各种方法，但无法解决问题。请有人帮我指出来。

我正在研究一些排序算法及其执行时间。我在 Python 中实现了一些算法，我正在测量它们对一些数组进行排序需要多长时间。我发现 Python 原生实现了 Timsort 作为列表的排序算法。但是，我想将原生 Timsort 与我在 GitHub 上找到的实现（这个）进行比较。本地实现怎么可能需要 0.000630140304565 秒来对 51200 个元素的数组进行排序，而我之前链接的实现需要 40.7546050549 秒来对同一个数组进行排序？

[编辑]为了获得时间，我在执行排序算法之前和之后使用“time.time()”，然后我只是有所作为。

我希望本机实现更快，但不是那么快。事实上，我还在 Python 中实现了其他排序算法，例如，Merge-Sort 需要 0.148133039474 秒来对同一个数组进行排序。我没想到 Merge-Sort 和 Timsort 的 Python 实现之间有这么大的区别。

[EDIT2] 所以问题是我发现的实现效率不高，也不是真正的 Timsort。抱歉，我刚刚发现 Timsort 是 theta(nlgn)，我相信这是正确的实现。现在的问题是：Timsort 的高效 Python 实现是否存在？

该算法在从 arrl 开始到 depr 结束的特定时间间隔内找到最重叠的活动（波段）。我使用快速排序来获得 O(nlogn) 时间复杂度，然后使用带有 O(n) 的 while 循环来计算冲突活动的数量这些间隔 1. 那么这是否像 O(nlogn) + O(n) 时间复杂度？2.我可以在 O(n) 时让它更快吗？3.最后，理论上，是否可以使用 Timsort 来获得 O(n) 时间复杂度？

用 C 编写的代码适用于 15 个活动，但假设它是通用的，并且带有未排序的 arrl 和 depr

编辑：结果是 1 小时内的活动最多

ArrayLists 似乎使用 TimSort 排序，其中底层列表在排序期间并不总是一致的。在调用比较器时，列表条目可能会消失或出现两次。

在我们的比较器中，我们正在比较键，我们正在使用一个函数来获取一个值来比较这个键。由于此函数在其他上下文中使用，我们测试了键是否实际存在于列表中（排序中不需要的东西）：

由于键是我们正在排序的列表，因此由于 TimSort 的内部机制，比较器可能会在列表中找不到键。

问题：这是否在 Javadoc 中的某处（找不到）提到您不应该访问 Comparator 中的底层列表？这是应该对副本进行排序的 TimSort 的糟糕实现吗？还是首先访问比较器中的基础列表是一个愚蠢的想法？

下面的程序由TJ Crowder提供，演示了底层列表的内容在调用 Comparator 期间可能不一致。（这个程序演示了有问题的现象，但它并不代表受问题影响的实际应用程序。）

以下是运行的前几行输出：

为什么会Collections.sort()创建一个额外的对象数组并对数组执行 Tim 排序，然后最终将排序后的数组复制回List对象？我知道这个调用针对 进行了优化LinkedList，但我们不会失去性能ArrayList吗？

我们本可以避免2n将其转换为对象数组并将它们添加回列表中的操作数。我知道这些额外的操作不会影响整个排序操作的 Big-O，但我相信它可以针对ArrayList.

我在这里错过了什么吗？我只是想理解为什么架构是这样布局的。谢谢。

https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/Collections.java#l164

I have seen a lot of similar questions here but none of them so far have answered the question directly, but instead have provided work arounds in specific scenarios to the asker's problem.

I would like a general answer to the question of breaking ties in Python's Timsort. Can it be done? If it can be done, what is the general method of doing that.

For example take the list of tuples

I want to sort these tuples such that their order is determined primarily by the value of the first value in each tuple. If we leave reversed=False, then they will be sorted by increasing order. I would do this with the following

The result will be

The question is what can I do general to break the tie between the first three elements. I would like to know if this is generally possible and applicable in any problem where defining a sort key comes up.

Most of the time the other answers will mention that Timsort is stable. Does this rule imply that it is not possible to break ties?

A 和 B 是堆栈上的相邻运行，A 是底部和较小的运行（如果 B 较小，merge_hi 将执行合并，但同样的问题也适用于那里）。我一直试图弄清楚为什么最后一个元素A 必须大于 B 的最后一个元素，因为我看不到运行分解（或算法的其余部分）如何确保该条件。此外，在同一个函数中，代码似乎表明 B 的第一个元素总是小于 A 的第一个元素，我也不明白为什么，但我猜这个问题的答案与答案有关第一个问题。

我正在尝试在 Java 中制作一个 timSort 版本，它在 array.length < 10 之后使用插入，否则使用合并排序。假设我对insertionSort 和merge 的调用是正确的，那么是什么阻止了以下内容的插入排序和正确的timSorting？

这种比较器方法有什么问题？

我已阅读： Java 错误：比较方法违反其一般合同

并且理解如果c1 > c2，并且c2 > c3，那么c1 > c3。我相信这在上面应该成立。

getMaxCosine() 返回 0..1 之间的值，第二次排序是按卡片中文本的长度，越长排名越高。