问Java，排序分析。Quicksort1，Quicksort2，Mergesort，给了一个黑匣子

EN

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

保持(stable/unstalbe)

• order的

1. 顺序:将不同的对象比较到彼此(或枢轴)的
2. 顺序，其中不同的对象被交换

。

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

class item {
  int sortid;
  string name;

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

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

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

快速排序的不同实现将首先尝试将对象移动到较小的对象(从左转到右)，因此如果您发现您的元素与第一个元素(如果是中间的话)是第一个实现，那么它就是快速排序的第二个实现。

要实现这一点，您需要传递具有自定义比较的对象，这将检查比较对象的元素，并且它们知道什么可以用作枢轴，所以第一次比较将给出哪种排序方法实际使用哪个枢轴。

此时，可以清楚地知道哪一个是堆，但是如果您有能力监视元素交换，您也可以检测堆，因为它首先开始放置最小/最大的元素。

如果您能够测量运行时间，那么一种方法是为每种算法构造最佳和最坏的输入，并查看哪些算法在哪种情况下减慢了运行速度，以及降低了多少。

• 最简单的情况是快速排序，选择第一个元素作为枢轴；当数组已经有序或反序时，这将退化为二次时间。最好的情况可以通过确保枢轴始终是子数组中元素的中值来构造。
• 下一个最简单的情况是使用数组的中间作为枢轴进行快速排序；对于某些输入，这同样会退化为二次时间，但是构造这样的输入要困难一些。最好的情况是数组已经有序或顺序相反，所以中间元素始终是中间元素。在最坏的情况下，
• 合并排序仍然是O(n log )，但在某些类型的输入上却要慢一些。当一个数组中的所有元素都小于另一个数组中的所有元素时，“合并”阶段进行的比较最少，而当两个数组在最坏的情况下仍然是O(n log )时，当两个数组被“交错”时，进行的比较最多，但也可以更快或更慢，这取决于每个元素必须“筛选”的范围。

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