java - 如何有效地对一个数组进行排序

Question

假设我有以下设置:

double[] vectorUsedForSorting = new double[] { 5.8,6.2,1.5,5.4 }
double[] vectorToBeSorted = new double[] {1.1,1.2,1.3,1.4}

我想根据 vectorUsedForSorting 的自然数字顺序对 vectorToBeSorted 进行排序。

例如，自然排序为 [1.5,5.4,5.8,6.2]，它对应于索引 [2,3,0,1]，这将意思是我希望排序函数的输出为 [1.3,1.4,1.1,1.2]。

我如何以最绝对有效/最快的方式做到这一点？我最关心的是时间复杂度，因为我将对 1,000,000 长度的数组执行此操作。

快速/高效的答案将获得巨额奖金。

Answer 1

简单的解决方案:

class D implements Comparable<D> {
    double key;
    double value;

    @Override
    public int compareTo(D other) {
        return Double.compare(key, other.key);
    }
}

public class Test {
    public static void main(String[] args) {
        double[] vectorUsedForSorting = new double[] { 5.8,6.2,1.5,5.4 };
        double[] vectorToBeSorted = new double[] {1.1,1.2,1.3,1.4};

        D[] array = new D[vectorUsedForSorting.length];
        for (int i = 0; i < array.length; i++) {
            array[i] = new D();
            array[i].key = vectorUsedForSorting[i];
            array[i].value = vectorToBeSorted[i];
        }

        Arrays.sort(array);

        for (int i = 0; i < array.length; i++) {
            vectorToBeSorted[i] = array[i].value;
        }

        System.out.println(Arrays.toString(vectorToBeSorted));

    }
}

这确实需要一些额外的内存用于辅助数组和对象，但在执行时间上应该接近最佳。