Java，排序分析。堆排序、快速排序 1、快速排序 2、合并排序、给定黑匣子

Question

我得到了一个名为 BlackBox.java 的 Java 类。该类中有四种排序方法，分别称为 sort1、sort2、sort3 和 sort4。假设我们有合并排序、堆排序、快速排序，以数组中的第一个位置作为基准(不使用 StdRandom.shuffle)，最后我们有快速排序，它取第一个和最后一个元素的中间并将其用作基准(也不使用 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 个主要区别:

1. 顺序保持(稳定/不稳定)
2. 不同对象相互比较(或数据透视)的顺序
3. 不同对象交换的顺序

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

class item {
  int sortid;
  string name;

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

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

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

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

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

此时就可以清楚哪个是堆，但是如果您有能力监视元素交换，您还可以检测堆，因为它开始将最小/最大的元素放在前面