问题标签 [timsort]

我已经实现了 TimSort，但我真的需要能够按不同的字段进行排序。例如，按字段 2 排序，然后是 1，然后是 3。我一般知道如何执行此操作，如果先前给定的字段排序相同，则按下一个字段排序，但我正在寻找一个具有更多详细信息的解决方案特别是对于 TimSort。

我正在阅读有关Timsort的信息。我遇到了以下句子

minrun 是从 32 到 64 的范围内选择的，因此数据的大小除以 minrun 后，等于或略小于 2 的幂。

为什么我们将最小运行规模保持为 2 的幂？如果我们选择这样的大小，是否会在内部进行任何特殊优化？请帮帮我。

我已经比较了 python 3 中一些内置排序函数的性能和一些我知道它们的性能的算法，我看到了一些意想不到的结果。我想澄清这些问题。

我使用“perfplot”库来比较可视化算法的复杂性。

我希望所有排序函数都接近 nlogn() 函数或至少比线性函数效率低，并且我希望“c_linear_inplace”会比“c_linear_outplace”快。但所有内置排序函数都比线性函数快得多，并且“c_linear_outplace”函数比“c_linear_inplace”函数慢。

编辑： 正如我所见，这些是具有常量的函数的复杂性：
sort，sort_c，builtin：c nlog ₂ (n) for c>=1
check：linear inplace：6n
check：linear not in place：7n
check： nlogn : 2n + 3n对数₂ n

我将任何 for 循环计算为 2*（迭代次数）以进行检查和增量。并且任何“if”都为 O(1)，任何赋值 (=) 为 O(1)，这似乎很奇怪，甚至占用更多内存的“check:linear not in place”比“check:linear inplace”的性能要好得多并且仍然比任何 numpy 的类型都差

在经典的合并排序算法中，在将元素重新合并在一起之前，通常会划分输入数组，直到它们具有几个单元素子数组。但是，众所周知，您可以通过拆分数组来修改此合并排序算法，直到您拥有 k 个子数组，每个子数组的大小为 n/k（n 是数组的原始长度）。然后，您可以使用插入排序对这 k 个子数组中的每一个进行排序，并使用 merge 子例程将它们合并。

直觉上，我认为在某些情况下这应该比合并排序更好，因为插入排序在小数组上很快。但我想准确地弄清楚这种混合算法何时优于常规合并排序算法。我不认为小 k 会更好，因为当 k 接近 1 时，我们只会使用插入排序算法。我认为有一些最佳比率 n/k，但我不太确定如何找到它。

任何帮助表示赞赏。

它发生在我的 Android 应用程序上，这是堆栈跟踪：

这是我的排序逻辑：

这是比较器：

我找到了相关的问题和其他解决方案，但没有一个能解决我的问题。此外，这不是一致的行为，而是仅发生在某些应用程序用户身上。

我正在尝试实现 Timsort 算法以将随机有符号整数排序为非递减顺序。当整数的数量相对较小时，该算法可以很好地对有符号整数进行排序，但是当数字变大时，当有符号整数的数量不是 2 的幂时，它似乎无法排序。

例如，它可以很好地对 256 个随机有符号整数进行排序，但无法对 257、258、259、260 或 261 个有符号整数进行排序。但是它对 512、511、510 个有符号整数进行了很好的排序。我找不到导致这种不一致结果的原因，对于某些不是 2 的幂的元素，它可以工作，而对于其他一些不是 2 的幂的元素，它会失败。

我已经为计算机科学课程编写了 Timsort 排序算法，我希望能够将运行时与其他类似算法进行比较，例如归并排序。但是，我不确定应该在代码中的何处放置计数（即：count +=1）以获得准确的运行时间。任何帮助将非常感激。

我知道这个问题可能有一些非常好的解释，但我仍然无法将它应用到我的代码中。在我的情况下如何避免该错误？这是我的代码：

sampleList 是一个类型的列表，其中包含字符串中的日期。这是我得到的一个例外：

如果您对如何解决它有任何建议，请与我分享。谢谢你。

我对排序算法有疑问。我正是使用这个 TimSort 来排序https://www.geeksforgeeks.org/timsort/ (Java)。例如，我正在前 2500 行的循环中读取 CSV 文件。

这是我的阅读代码：

之后，我以这种方式将字符串转换为 int[] Arraylist：

在我的主要我有：

并运行它：

现在， 如果我通过将循环更改为 i > 0 && i <= 1000 来运行此代码，它就可以工作了。但是，如果我采用更大的数字，例如 2500 或 5000，我会收到以下错误：

它引用了 TimSort 算法中的合并方法......我无法解决这个问题，请问有什么想法吗？

我正在开发一个旧应用程序，它最初是用 Java 6 编写的，几年前升级到 Java 7。

在这个应用程序中，我使用 Collection.Sortcompare通过实现Comparator接口使用自定义方法对列表进行排序。列表中的对象类型有CompanySchedule3 个属性companyName和。 Scheduleexpirationdate

列表可以包含多个具有相同companyName但具有唯一到期日期的对象。下面的比较函数按公司名称的升序对列表进行排序，并在同一公司名称列表中按到期日期的降序对列表进行排序。下面是方法实现。

我知道在上面的比较方法实现中不满足传递属性时 java.lang.IllegalArgumentException: Comparison method violates its general contract会抛出错误。

有人可以帮助确定此方法在何处违反传递性。谢谢您的帮助。