Java，排序分析。 Heapsort，Quicksort 1，Quicksort 2，Mergesort，给定一个黑盒子

Question

我在 Java 中得到了一个 class，叫做 BlackBox.java。 class中有四种排序方法，分别称为sort1、sort2、sort3和sort4。假定我们有 Mergesort、Heapsort、Quicksort，以数组中的第一个位置作为基准（不使用 StdRandom.shuffle），最后我们有 Quicksort，它取第一个和最后一个元素的中间并将其用作基准（也不使用 StdRandom.shuffle）。

问题是我需要找出排序方法（sort1、sort2、sort3、sort4）是什么。我已经计算了输入 500.000 个整数的时间。首先我使用随机排序的输入，然后我使用定期排序的输入，然后我使用反向排序的输入，最后我使用一个非常大的输入，整数相同，到处都是 3 ({3 3 3 3 3...})。有时我得到堆栈溢出，有时却没有。我对它们的排序时间也非常相似，我的意思是非常相似，我无法用它来判断我使用的是哪种排序算法。

我怎样才能找出哪个算法是什么？我应该使用什么方法？

P.s。我已经阅读了 Sedgewick 和 wayne 编写的算法一书中的第 1.4 章，并在互联网上进行了大量搜索。也许我对第 1.4 章的理解还不够。所以，如果可以的话，我请你帮我解决这个问题。

另外，我没大声检查字节码

Answer 1

所有这些算法之间有 3 个主要区别：

顺序保留（stable/unstalbe）
不同对象相互比较（或枢轴）的顺序
交换不同对象的顺序

要测试顺序保留，您需要使用一个属性对对象进行排序，第二个用于区分它们，例如：

class item {
  int sortid;
  string name;

  compareTo(item) -> return compare(this.sortid, item.sortid); note that name is not used
}

因此，通过提供具有非唯一 sortid 但不同名称的数组，您可以检查算法的稳定性，请注意 - 您需要使用多个输入来查看稳定性，因为即使是不稳定的输入也可能 return稳定订单：

合并 - 稳定
堆 - 不稳定
快 - 不稳定

快速排序的不同实现将首先尝试将较小的对象移至左侧，将较大的对象移至右侧，因此如果您发现您的元素与第一个元素进行比较 - 它是第一个实施的枢轴，如果与中间- 这是快速排序的第二次实现

要实现这一点，您需要传递具有自定义比较的对象，这将检查它们与哪个元素进行比较并且它们知道什么可以用作枢轴，因此第一次比较会给您答案实际使用哪个枢轴哪种排序方式

此时可以清楚哪个是堆，但是如果你有能力监控元素交换，你也可以检测到堆，因为它开始将 smallest/largest 个元素放在第一位

Answer 2

如果您能够测量运行时间，那么一种方法是为每个算法构建最佳和最差情况输入，并查看哪些输入在哪些情况下变慢，以及减慢多少。

最简单的情况是快速排序选择第一个元素作为基准；当数组已经有序或以相反的顺序排列时，这会降级为二次时间。最好的情况可以通过确保枢轴始终是该子数组中元素的中位数来构造。
下一个最简单的情况是使用数组的中间作为基准的快速排序；对于某些输入，这同样会退化为二次时间，但构建此类输入有点困难。最好的情况是当数组已经有序或倒序时，使得中间元素总是中位数。
归并排序在最坏的情况下仍然是 O(n log n)，但在某些类型的输入上速度较慢。 "merge" 阶段在一个数组中的所有元素都小于另一个数组中的所有元素时进行最少的比较，而在两个数组尽可能"interleaved" 时进行最多的比较。
Heapsort 在最坏的情况下仍然是 O(n log n)，但同样可以更快或更慢，具体取决于每个元素必须有多远 "sifted down"。

这可能比使用自定义比较器监视算法的内部工作更难，该比较器记录以什么顺序比较哪些元素，但我认为这更有可能是您的教授想要的解决方案。

Java，排序分析。 Heapsort，Quicksort 1，Quicksort 2，Mergesort，给定一个黑盒子

Java, sorting analysis. Heapsort, Quicksort1, Quicksort2, Mergesort, given a blackbox

java

algorithm

sorting

black-box-testing