Java：使用indexOf方法根据另一个数组对数组进行排序

Question

我想根据另一个数组(indexes)的排序顺序(此案例为10，34，32，21)，来遍历两个数组(A和B)。

String[] A: a, b, c, d
String[] B: e, f, g, h
int[] indexes: 10, 34, 32, 21

很抱歉这里的示例不好。我已经更新了索引数组以消除混淆。

期望输入和输出

输入是三个数组。我想通过索引数组的排序来迭代A、B。也就是说，我想找到一种迭代方式，使用顺序(a, d, c, b)迭代A，使用顺序(e, h, g, f)迭代B。

我的方法：

我用了一种解决问题的方法，我相信它与另一种方法是完全相同的。然而，第二种方法不起作用。如果有人能解释为什么它不起作用，我会很感激，因为我认为这会让我更好地理解java中Collections.sort的工作原理。

List<Integer> indexOrder = new ArrayList<>(indexes.length);

for (int i = 0; i < indexes.length; i++) {
    indexOrder.add(i);
}

Collections.sort(indexOrder, Comparator.comparing((Integer s) -> indexes[s]));

受这个主题的启发，我创建了一个ArrayList（更喜欢AList而不是数组），其值为（1,2,3... indexes.length），然后使用与索引相关的比较器将其排序。上述代码按预期工作。 但是，如果我将最后一行中的indexes[s]更改为indexes[indexOrder.indexOf(s)]。排序将产生错误结果。如果ArrayList的索引与其值相同，为什么indexOf（s）会给出不同的结果？

Collections.sort(indexOrder, Comparator.comparing((Integer s) -> indexes[indexOrder.indexOf(s)]));

- chakwok

---

你的输入和期望输出是什么？ - Ravindra Ranwala

我不太确定你的问题是什么，但为什么不直接使用 for (int idx : indexes) { ... A[idx] ... B[idx] ...} 呢？ - Henry

你的 indexOrder 中是否有重复项或者是稀疏的？ - ernest_k

不，indexOrder中没有重复项。它的值只是0、1、2、3……indexes.length的索引。 - chakwok

@DodgyCodeException 是的，这三个数组长度相同。 - chakwok

Answer 1

你可能期望indexOrder.indexOf(s)总是等于s(因为你的List被初始化为[0, 1, 2, 3]，其中s的索引是s)。

虽然在原始的indexOrderList中这是正确的，但当 Collections.sort 开始交换你的List元素时，这个假设可能不再成立。

为了在排序List时不依赖于indexOrder的顺序，你可以创建那个List的副本:

List<Integer> copy = new ArrayList<>(indexOrder);
Collections.sort(indexOrder, Comparator.comparing((Integer s) -> indexes[copy.indexOf(s)]));

- Eran

Answer 2

由于索引中存储的最大值不超过1000，我觉得这种排序算法（它是计数排序的一种变体）将是最佳选择。

final String[] A = { "a", "b", "c", "d" };
final String[] B = { "e", "f", "g", "h" };
final int[] indexes =  { 10, 34, 32, 21 };

// find out the max value in the array.
// The loop can be skipped with maxIndexValue = 1000; but i would most likely save some memory using the loop.
// Can also be replaced with : IntStream.of(indexes).max().getAsInt(), with such a small set of data it won't hurt performance that bad
int maxIndexValue = 0;
for (int indexValue: indexes) {
    if (maxIndexValue < indexValue) {
        maxIndexValue = indexValue;
    }
}
maxIndexValue += 1;

final String[] indexSortedA = new String[maxIndexValue];
final String[] indexSortedB = new String[maxIndexValue];
System.out.println(maxIndexValue);
// each value of A (and B) will be put at indexes position, it will result in a appropriately sorted arrays but with a lot of whitespace.
for (int i = 0; i < indexes.length; ++i) {
    indexSortedA[indexes[i]] = A[i];
    indexSortedB[indexes[i]] = B[i];
}

// Create final arrays by filtering empty values
final String[] sortedA = Arrays.stream(indexSortedA).filter(v -> v != null && !"".equals(v)).toArray(String[]::new);
final String[] sortedB = Arrays.stream(indexSortedB).filter(v -> v != null && !"".equals(v)).toArray(String[]::new);

该算法的复杂度为：O(n) + O(1000) + O(2n)。虽然会占用更多内存，但比任何 Collection.sort() 都要好。

- Anthony Raymond

---

哦，确实。这些数字是否已知在一个短区间内，还是可以是整个整数范围？ - Anthony Raymond

@Andyk。根据这个限制，我已经更新了我的答案。 - Anthony Raymond

喜欢你解决这个问题的方法。感谢分享。 - chakwok

我明白这是如何工作的，应该非常快。顺便说一下，获取最大索引值的可能更简洁（也可能更易读）的方法是：final int maxIndexValue = IntStream.of(indexes).max().getAsInt(); - DodgyCodeException

我认为你的算法是计数排序的一种变体，因为没有重复项，所以计数要么是0要么是1。 - DodgyCodeException

Answer 3

我尝试运行了这段代码，两种情况下得到的结果都相同。

情况1：

public static void main(String[] args) {
    String[] A = { "a", "b", "c", "d" };
    String[] B = { "e", "f", "g", "h" };
    int[] indexes = { 0, 4, 2, 1 };

    List<Integer> indexOrder = new ArrayList<>(indexes.length);

    for (int i = 0; i < indexes.length; i++) {
        indexOrder.add(i);
        System.out.println(i);
    }

    //Collections.sort(indexOrder, Comparator.comparing((Integer s) -> indexes[s]));
    Collections.sort(indexOrder, Comparator.comparing((Integer s) -> indexes[indexOrder.indexOf(s)]));

    System.out.println(indexOrder.toString());
}

输出： 0 1 2 3

[0、3、2、1]

第二种情况：

public static void main(String[] args) {
    String[] A = { "a", "b", "c", "d" };
    String[] B = { "e", "f", "g", "h" };
    int[] indexes = { 0, 4, 2, 1 };

    List<Integer> indexOrder = new ArrayList<>(indexes.length);

    for (int i = 0; i < indexes.length; i++) {
        indexOrder.add(i);
        System.out.println(i);
    }

    Collections.sort(indexOrder, Comparator.comparing((Integer s) -> indexes[s]));
    //Collections.sort(indexOrder, Comparator.comparing((Integer s) -> indexes[indexOrder.indexOf(s)]));

    System.out.println(indexOrder.toString());
}

输出： 0 1 2 3

[0, 3, 2, 1]

- Uday Kumar