我正在开展一项活动，在该活动中，我必须确定在一组给定方法中使用哪种排序，因为它是从仅包含 .class 文件的 .jar 文件运行的，所以我实际上无法查看。我所能看到的只是时间信息（所以我可以根据时间复杂度确定它可能是什么类型）。但是，被排序的元素是随机生成的整数，并且允许重复。为了正确识别排序，我必须以某种方式识别哪些方法没有以稳定的方式排序——无法查看源代码或整数数组。例如，我可以有一个数组 [1,2,3,9,5,64,8,5,1]，排序后将是 [1,1,2,3,5,8,9,64] . 但是，如果使用诸如非稳定选择排序之类的方法对其进行排序，则两个 1 值将按照彼此的相对顺序进行切换。
问问题
2094 次
2 回答
2
如果您受限于使用ints，则无法对其进行测试，因为无法区分两个不同1的 s。
但是，如果您有使用的选项Integers，并且您专门使用new Integer()（而不是 Java 附带的自动装箱），则可以将原始数组中的引用与新数组中的引用进行比较。
于 2016-09-26T21:46:42.307 回答
1
正如 Joe C 所提到的，您将不得不使用某种包装类，因为无法确定两个原始值之间的差异。例如，可以使用 Integer 类。
然而这里有一个更大的问题，这是一个逻辑问题。仅仅因为排序算法不能保证是稳定的，并不意味着给定一个特定的输入它会不稳定。因此，测量算法的不稳定性最终是确定正在使用哪种算法的不可靠方式。
您可以使用不稳定性来缩小潜在算法的范围，但首先我建议您关注不同算法处理不同类型输入所需的时间。从显而易见的算法时间复杂度开始：例如，bogosort平均需要比快速排序更长的时间。然后深入研究您正在考虑的算法的内部工作原理。一些具有相同时间复杂性的算法（例如：mergesort 和 heapsort）都会根据您传递给它们的输入类型而表现不同。例如，一个人处理完全反转的输入可能非常慢，而另一个人可能会很快完成。
于 2016-09-26T23:17:02.457 回答