我们能知道一个集合是否几乎被排序而不应用排序算法吗？
所以我的问题是：如果不先使用排序algoithm对列表进行排序，如何知道该列表是否接近排序呢？
共有1个答案
你熟悉一般的排序下界吗？您可以证明，在基于比较的排序算法中，任何排序算法在平均情况下都必须进行Ω(n，log，n)比较。你证明这一点的方法是通过信息论的论证。基本思想是有N！输入数组的可能排列，因为唯一的方法是进行比较，所以至少要做lg n！比较，以确定您知道您的输入排列的结构。
我还没有算出这方面的数学，但我怀疑你可以提出类似的论点来表明，很难了解特定数组的排序方式。本质上，如果你不做大量的比较，那么你就不能区分一个基本上是排序的数组和一个实际上离排序很远的数组。因此，我所知道的所有算法都需要花费相当多的时间来度量“排序”。
例如，数组中“排序”级别的一个度量是该数组中的反转次数。您可以使用基于mergesort的分而治之算法在时间O（n log n）中计算数组中的反转次数，但使用该运行时，您可以只对数组进行排序。
-
注意：我不想使用任何库。试图解决https://icpc.kattis.com/problems/stacking 在以下条件下，合并排序数组所需的最小操作数是多少： 拆分：可以将单个堆栈拆分为两个堆栈，方法是将堆栈的任何顶部提起并放在一边，形成一个新堆栈。 连接：两个堆栈可以通过将一个放在另一个上面来连接。仅当顶部堆叠的底板不大于底部堆叠的顶板时，才允许这样做，也就是说，必须正确订购连接的堆叠。
-
我正在尝试实现一个不能正常工作的mergesort算法。合并排序的工作方式如下： i、 将未排序的列表划分为n个子列表，每个子列表包含1个元素（1个元素的列表被视为已排序）。 ii.重复合并子列表以产生新排序的子列表，直到只剩下1个子列表。这将是已排序的列表。下面提供了实现。 最初，递归调用此方法，直到只有一个元素。 这是提供的合并方法。 这里的问题是什么？ 输入是输出是
-
问题内容： 我有一个Java集合： 现在在显示列表之前有一个字段，我想按此排序此集合。 有什么办法可以做到吗？ 问题答案： 使用比较器： 此外，如果实现，则只需使用 使用JDK 8，语法要简单得多。 更简单 最简单的 显然，初始代码也可以用于JDK 8。
-
问题内容： 我找不到使用此方法的任何示例，所有示例都给出了第二个参数“ null”。我听说此方法用于根据多个标准对类进行排序，但找不到示例。 对于本课程，如果我想根据学生的姓名和年龄对学生列表进行排序，如何使用方法Collections sort（List，Comparator） 问题答案： 在你现有的学生班级的基础上，这通常是我的工作方式，尤其是当我需要多个比较器时。 用法： 编辑 自Java
-
主要内容：1 集合元素的排序,2 Collections sort方法,3 字符串正序排序,4 字符串倒序排序,5 包装类型排序,6 自定义对象排序1 集合元素的排序 我们可以对以下元素进行排序： 字符串对象 包装类对象 用户自定义对象 Collections类提供用于对集合的元素进行排序的静态方法。如果集合元素为Set类型，则可以使用TreeSet。但是，我们无法对List的元素进行排序。Collections类提供用于对List类型元素的元素进行排序的方法。 2 Collections so
-
这是我面试问题的一部分。 给定一个整数序列作为一个数组，我必须确定是否可以通过从数组中移除不超过一个元素来获得一个严格递增的序列。 例如， 对于，输出应该是