java - 如何有效地根据其内容排序修改数组的内容？

Question

我有一个关于数组的问题。例如，如果我知道数组的大小为 5，并且我的程序读入

[9993, 1000, 9992, 3, 872] 

进入数组，如何有效地编辑数组的内容，使其变为

[5, 3, 4, 1, 2]

我只能实现一个以 O(n^2) 运行的双 for 循环。我希望找到一个更好的算法。

有什么提示吗？提前致谢！

Answer 1

一种选择是开设这样的课程：

class Tuple implements Comparable<Tuple> {
    int value;  // value
    int pos;    // position in array

    public Tuple(int value, int pos) {
        this.value = value;
        this.pos = pos;
    }

    @Override
    public int compareTo(Tuple other) {  // sort based on values
        return Integer.compare(value, other.value);
    }
}

然后：

Tuple[] tups = new Tuple[array.length];

for (int i = 0; i < array.length; i++)
    tups[i] = new Tuple(array[i], i);

Arrays.sort(tups);

for (int i = 0; i < array.length; i++)
    array[i] = tups[i].pos + 1;

由于数组排序，这是一个 O(n log n) 过程。

Answer 2

为此，您必须使用一种排序算法，因此您可以获得的最佳运行时间是 O(n logn)。如果您搜索它们，您可以在网上找到很多排序算法。我建议初学者学习的最快的是 Quicksort、Mergesort 和 Heapsort。