java - 测试 Array 是否已排序或仅对其进行排序并从那里开始是否更有效？

Question

我编写了一种方法来找到我一无所知的数组中的中位数，除了它带有双打。它也在工作，但由于我不知道它可能有多大，我想知道我正在做的事情是否有效。如果数组未排序而不是直接排序，我应该检查它吗？或者如果我无论如何都要对它进行排序，那会是一个不必要的步骤吗？是我推荐的排序方式还是我错过了更好的方式？

//I calculate the median and return it.
public static double median(double[] vals) { //(un-)sorted Array
    double median = 0;

    sortedVals = Arrays.stream(vals).sorted().toArray(); //sorts low to high

    int middleOfArray = (sortedVals.length) / 2 - 1;
    int secondMiddleOfUnevenArray = (sortedVals.length) / 2;

    if(sortedVals.length % 2 == 1) { //uneven values in Array
        median = sortedVals[middleOfArray] + 1;
    } else if(sortedVals.length % 2 == 0) { //even values in Array
        median = (sortedVals[middleOfArray] + sortedVals[secondMiddleOfUnevenArray]) / 2;
    } else {
        System.out.println("Method median: error");
    }
    return median;
}

标签： javaarraysperformancesorting

Answer 1

这似乎是一个基于意见的问题，但从技术上讲，检查输入数组是否已排序可能是有意义的——它具有线性 O(N) 复杂性，对于随机输入，只需检查几个元素。

public static boolean isSorted(double ... arr) {
    if (arr == null) {
        return false;
    }   
    int currOrder = 0;
    for (int i = 1; i < arr.length; i++) {
        int nextOrder = Double.compare(arr[i], arr[i - 1]);
        if (currOrder == 0) currOrder = nextOrder;
        if (nextOrder != 0 && nextOrder != currOrder) {
            // System.out.println("Non-sorted at index=" + i + ": " + Arrays.asList(arr[i - 2], arr[i - 1], arr[i])); // log message
            return false;
        }
    }
    
    return true;
}

接下来，最小长度为 2 的数组似乎存在中位数，因此需要对其计算进行固定：

public static Double median(double ... vals) { //(un-)sorted Array
    if (vals == null || vals.length < 2) {
        return null; // or throw some exception
    }
    if (!isSorted(vals)) {  // O(N)
        Arrays.sort(vals);  // O(N log N)
    }

    int mid = vals.length / 2;
    if(vals.length % 2 == 1) { //uneven values in Array
        return vals[mid];
    }
    // avoid addition overflow
    return vals[mid - 1] / 2 + vals[mid] / 2;
}

测试：

System.out.println("between max even: " + median(Double.MAX_VALUE, Double.MAX_VALUE));

System.out.println("between max  odd: " + median(Double.MAX_VALUE, Double.MIN_VALUE, Double.MAX_VALUE) + "; MAX=" + Double.MAX_VALUE);

System.out.println("odd : " + median(1, 400, 50, 50, 100000));
System.out.println("even: " + median(1, 3, 50, 100000));
System.out.println("even: " + median(-1, -2, -50, 100000));

输出（启用日志）：

between max even: 1.7976931348623157E308
Non-sorted at index=2: [1.7976931348623157E308, 4.9E-324, 1.7976931348623157E308]
between max  odd: 1.7976931348623157E308; MAX=1.7976931348623157E308
Non-sorted at index=2: [1.0, 400.0, 50.0]
odd : 50.0
even: 26.5
Non-sorted at index=3: [-2.0, -50.0, 100000.0]
even: -1.5