0

我想实现合并排序，但在这种情况下我需要保护的最大值。我厌倦了使用 null 作为最大值，但我得到空指针异常。

 private static <T extends Comparable<? super T>> void merge(T[] A, int p, int q, int r) {

        T[] L = Arrays.copyOfRange(A, p, q + 1);
        T[] R = Arrays.copyOfRange(A, q, r + 1);


        L[L.length - 1] = null; //guard
        R[R.length - 1] = null; //guard


        int i = 0; 
        int j = 0; 
        // i+j < r - k
        for (int k = p; k < r; k++) {            
            if (L[i].compareTo(R[j]) <= 0) {
                A[k] = L[i];
                i++;
            }
            else {
                A[k] = R[j];
                j++;
            }
        }
    }

所以我定义

Comparable<T> guard = new Comparable<T>(){

    @Override
    public int compareTo(T o) {
        return 1; //always max
    }};

    L[L.length - 1] = (T) guard;
    R[R.length - 1] = (T) guard;

但是如果我用它作为守卫而不是 null 我可以重写代码但我总是得到 ArrayStoreException

如何以正确的方式做？

所以问题是：如何在不知道 T 是什么的情况下定义与 T 类型具有可比性的对象。

4

2 回答 2

0

定义总是返回 1 的比较器是个坏主意，它不符合比较器的要求。

你总是知道守卫在哪里，所以你可以检查索引或者你可以检查空值。因此，只需添加特殊逻辑，如果元素是守卫，它将绕过比较器。
像这样的东西：

 for (int k = p; k < r; k++) {            
      if (R[j] == null || (L[i] != null && L[i].compareTo(R[j]) <= 0)) {
          A[k] = L[i];
          i++;
      }
      else {
          A[k] = R[j];
          j++;
      }
 }
于 2013-11-08T08:33:18.670 回答
0

您不能使用 null，如果要对正值或非常大的值进行排序，则使用 -1

代替

    L[L.length - 1] = null; //guard
    R[R.length - 1] = null; //guard

利用

    L[L.length - 1] = -1; //guard
    R[R.length - 1] = -1; //guard
于 2013-11-08T07:24:32.223 回答