时间戳

首页 > 解决方案 > Java，排序分析。Heapsort，Quicksort1，Quicksort2，Mergesort，给定一个黑盒

java - Java，排序分析。Heapsort，Quicksort1，Quicksort2，Mergesort，给定一个黑盒

问题描述

我得到了一个名为 BlackBox.java 的 Java 类。该类中有四种排序方法，分别称为 sort1、sort2、sort3 和 sort4。假设我们有合并排序、堆排序、快速排序，数组中的第一个位置作为枢轴（不使用 StdRandom.shuffle），最后我们有快速排序，它取第一个和最后一个元素的中间并将其用作枢轴（也不使用 StdRandom.shuffle）。

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

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

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

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

标签： javaalgorithmsortingblack-box-testing

解决方案

所有这些算法之间有 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 但名称不同的数组，您可以检查算法的稳定性，注意 - 您需要使用多个输入来查看稳定性，因为即使是不稳定的输入也可能返回稳定的顺序：

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

快速排序的不同实现将首先尝试将对象移动到更小的向左和更大的向右旋转，所以如果你发现你的元素与第一个元素进行比较 - 这是枢轴的第一个实现，如果是中间 - 这是第二个实现快速排序

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

此时会很清楚哪个是堆，但是如果您有能力监视元素交换，您还可以检测堆，因为它开始首先放置最小/最大元素

推荐阅读