问题标签 [timsort]

对包含 2 个已排序子数组的数组进行排序最优化的排序算法是什么？

当我解决这个问题时出现了：https ://leetcode.com/problems/squares-of-a-sorted-array/

我的解决方案如下：

然而，这个解决方案胜过我的：

如果 timsort 对小块进行插入排序，那么这样的数组不会在一半的运行中导致 O(n^2) 吗？这比我所谓的 O(n) 解决方案好多少？

谢谢！

在TimRun 文档的“计算 minrun”部分，它给出了为 N=2112 数组选择 minrun 的一个好例子和一个坏例子。它指出使用 minrun = 32 效率低下，因为

长度为 2048 和 64 的运行最终合并 自适应噱头可以通过少于 2048+64 次比较来做到这一点，但它仍然比必要的比较多，并且 - 合并排序相对于样本排序的错误 - 更多的数据移动（O (N) 复制只是为了让 64 个元素到位）。

它还将 minrun = 32 算法描述为：

然后我们有一个类似于“2112”的案例，再次为最后一次合并留下了太少的工作要做

然后它表示选择 minrun = 33 将得到一个更好的完美平衡合并。

如果我们在这种情况下采用 minrun=33，那么我们很可能最终得到 64 次运行，每个运行长度为 33，然后所有合并都是完美平衡的。更好的！

我的问题是，如果总元素数相同（示例中为 2112），为什么合并完美平衡的排序数组比不平衡数组更好？

当 minrun=33 的总元素也是 2112 时，为什么 minrun=32 “做的比较比必要的多”？

为什么会有“更多的数据移动”？

为什么最后一次合并“工作太少”？

我的理解是，合并大小为 A 和大小 B 的排序数组需要 O(A+B)。为什么 A 和 B 大小相同时效率更高？

我绘制了如何执行 2 个 minrun 场景的图表，但我仍然感到困惑。

我现在正在学习 TimSort，并且遇到了它在不同编程语言中的实现。但其中一些似乎被“剃光”了——缺少某些对构成 TimSort 至关重要的功能。我看过原作者 Tim Peters 的原始 C 实现，以及 Joshua Blancs 的 java 重写？但是有一些符号和方法我很难掌握（只是我，还是看起来不可读？）

无论哪种方式，这是我找到并修改的代码，但它缺少识别自然增加的运行或反转减少的运行，检查不变的 C>B+A、D>C+B 等是否几乎/完美地合并实现了相等、平衡的子阵列，以及著名的驰骋功能。我可以帮助以更易读的方式实现它们吗？考虑到它可以是 [32-65]，runSize 是 32 还是 64 更好？谢谢你。

我的代码：

Joshua Bolch 在 java 中的实现： https ://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/TimSort.java

我没有在我的 Java 代码中使用任何比较器/排序，它仍然在抛出“java.lang.IllegalArgumentException：比较方法违反了它的一般合同！” 例外。

下面是调试时在 restTemplate.exchange 行上引发异常的一段代码。

当我将 spring-boot-starter-parent 的版本从 2.3.9 更改为 2.5.3 时开始出现此异常

我应该如何解决这个问题？

堆栈跟踪：

Consider I have a library call which accepts:

1. a list of items (of mixed/multiple types T1, T2, T3,..), and
2. a custom comparator C,

and, in addition to doing some work, sorts the list it accepts (first by type, and then using the custom comparator C).

Now, I need items of type T1 sorted by type and then using the custom order, while items of all other types (T2, T3,..) sorted by type only (i. e., once sorted by type, consequently sorted only with a no-op, order-preserving comparator).

In other words, I need smth like this (T1 is java.lang.Integer, T2 is java.lang.String):

The above code, when run, will produce the following output:

Now, provided that both Merge Sort and Timsort algorithms (used by the JDK to sort non-primitives) are stable, is it okay for my custom comparator to return 0 for the pairs where the order should be preserved?

Do any other alternatives exist?

我刚刚遇到错误，并且在排序之前我还使用了这个 System.setProperty("java.util.Arrays.useLegacyMergeSort", "true") 但仍然遇到相同的错误。

以下是比较器比较值

和 Balance 是具有一个平衡字段的类，我也有 Balance 列表，它的大小超过一千，以下是我的流。

仍然得到同样的错误。