1

作为示例，我正在用 java 开发一个简单的 MySortedSet，它实现了 SortedSet 接口。它由一个简单的数组备份，即 E[] 数组。

我对此有几个问题：

这是类：（我不是在编写整个代码，而是在编写相关部分）

public class MySortedSet<E> implements SortedSet<E>, Iterator<E> {

 private E[] array;
 private Comparator<? super E> _comparator;
 private int size = 0;
 private int capacity;

 @SuppressWarnings("unchecked")
 public MySortedSet() {
    this.capacity = 10;
    this.array = (E[]) new Object[this.capacity];
    // this.array = Array.newInstance(Class<E> var,int size);
    // We have to get Class<E> from outside caller.
 }
}

问题 3：对 Constructor 有一个解释，因为这是一个排序集，所以假设元素是排序的：

如果此构造函数用于创建排序集，则假定元素使用它们的自然顺序进行排序（即，E 实现 Comparable）。

它有两个不同的构造函数。一种是无参数的，另一种是接受的Comparator<? super E>。

public MySortedSet() {
    this.capacity = 10;
    this.array = (E[]) new Object[this.capacity];
    // this.array = Array.newInstance(Class<E> var,int size);
    // We have to get Class<E> from outside caller.
}

public MySortedSet(Comparator<? super E> comparator) {
    this._comparator = comparator;
}

如果comparator未传入，则应使用自然排序，但我不确定如何完成它，因为我需要以Comparator某种方式访问compare​​方法。请你们推荐我一种调用它的方法，这样我就可以在比较sort方法对每个元素进行排序时调用它。

对于他们喜欢查看完整代码的人，请参阅此地址：http ://codepaste.net/4ucvsw它并不完美，但我正在努力。

问题 4：代码指南说：

因为搜索特定项目的最快方法是使用二进制搜索，所以您必须确保集合中的项目始终处于排序顺序。这并不像看起来那么难实现。当您插入一个新项目时，您可以假设要插入它的数组已经排序。因此，您需要做的就是在数组中找到新项目所属的位置，将大于新项目的所有内容向右移动一个插槽，然后插入新项目。这称为插入排序。

这是sort方法逻辑。我需要进行二进制搜索以查找新项目所属的位置，以便我可以在该位置插入新项目并将另一个插槽向右移动。

但我不太确定二分搜索在这里对我有用，因为我不太确定我需要找到什么。我得到的是要添加的项目，而不是要查找的项目。相反，我认为是将每个元素与我需要添加的元素进行比较，当我找到最后一个较小和第一个较大的项目时，我将获得第一个较大项目的索引，将它们向右移动并在索引处添加新项目.

4

2 回答 2

1

答案 3：

“自然排序”意味着元素必须实现Comparable，以便可以在不使用 a 的情况下对它们进行比较Comparator。让调用者在Comparable元素和 a之间进行选择的棘手部分Comparator是，您无法进行编译时检查以确保它们至少满足其中一个要求。

JavaTreeSet类似地公开了一个构造函数，该构造函数接受 aComparator和其他不接受的构造函数。TreeSet的合同本质上是抛出 ​​aClassCastException如果您尝试插入一个不是 a 的元素，如果您在创建它时Comparable没有提供TreeSeta 。Comparator是否要使用此策略或其他策略取决于您。

答案 4：

根据报价的策略，您应该能够Arrays.binarySearch(Object[], Object)用于此确切目的。从该方法的文档中：

返回：搜索键的索引，如果它包含在数组中；否则，(-(insertion point) - 1)。插入点定义为将键插入数组的点：第一个元素的索引大于键，或者a.length如果数组中的所有元素都小于指定的键。请注意，这保证了当且仅当找到键时，返回值将 >= 0。

于 2012-05-28T02:38:29.080 回答
1

问题 3：

事实是每个集合都使用预定义的比较器，该比较器隐式定义在 上E，因此每个用于具体化类型参数的类E都应该implement Comparable<E>. 您正在寻找自然排序的比较方法是方法

int compareTo(E other)

这必须由您将与数据结构一起使用的类来实现。由于您的工作与定义要与您的集合一起使用的类无关，而只是集合本身您将要做的事情

public class MySortedSet<E> ... {
    private Comparator<? super E> _comparator;

    public int innerCompare(E e1, E e2)
    {
      if (_comparator != null)
        return _comparator.compare(e1,e2);
      else
        return e1.compareTo(e2);
    }

    ...

这样您就可以在提供时使用自定义比较器，否则使用自然比较器。

两者都Comparable遵循Comparator相同的原则，但第一个，顾名思义，附加到数据类，因此它是它的自然比较器。相反，使用后者是因为它允许您定义一种自定义方式来对元素进行排序，这些元素将根据自然顺序以不同的方式进行排序。

问题4：

这意味着，在具有排序数组的假设下，您必须在每次插入后保持此约束有效，并且您将被允许在查找项目时进行二进制搜索。

您必须只专注于将元素放置在正确的索引处（您必须添加的项目）。与查找元素相关的语句部分必须按以下方式解释：

如果您注意保持数组排序，这可以通过确保您添加的每个元素都放置在正确的位置来完成（例如，使用插入排序），那么您可以在查看元素是否包含在数组中时应用二进制搜索集。

这是正确的，因为如果对数组进行了排序，您可以确定查看数组部分的中间元素将始终指向正确的方向，以查看列表中是否确实包含另一个元素。

例如：

1, 2, 6, 11, 21, 30, 45

您需要检查 2，您可以在 index 处取元素size()/2 = 3，即11. 由于您已经知道数组已排序，因此2 < 11您可以在左半边递归地执行相同的操作，依此类推。

于 2012-05-28T02:41:12.353 回答