Java: 使用 indexOf 方法基于另一个数组对数组进行排序

Question

我想根据另一个数组（索引）的排序顺序遍历两个数组（A、B），在本例中为 10、34、32、21。

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

Apology for the bad example here. I have updated the indexes array to clear the confusion.

预期输入和输出

输入是三个数组。我想使用索引数组的排序来遍历 A、B。即我想找到一种使用顺序 (a, d, c, b) 迭代 A 并使用顺序 (e, h, g, f)

迭代 B 的方法

我的做法：

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

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]));

受 this thread 的启发，我创建了一个值为 (1, 2, 3...indexes.length) 的 ArrayList（更喜欢 AList 而不是数组），然后使用带有 ref 的比较器对其进行排序。到索引。 以上代码按预期工作。

但是，如果我将最后一行末尾的 indexes[s] 更改为 indexes[indexOrder.indexOf(s)]。排序会给出错误的结果。如果 ArrayList 的索引与其值相同，为什么 indexOf(s) 给出的结果与 s 不同。

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

Answer 1

您似乎希望 indexOrder.indexOf(s) 始终等于 s（因为您的 List 已初始化为 [0, 1, 2, 3]，其中 s 的索引是 s)。

虽然这在您的原始 indexOrder List 中是正确的，但当 Collections.sort 开始交换您的 List.

的元素时，这可能不再正确

为了在排序时不依赖 indexOrder 的顺序，您可以创建 List 的副本：

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

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() 但它会花费更多的内存。

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]

案例 2：

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]

Java: 使用 indexOf 方法基于另一个数组对数组进行排序

Java: Sorting an array based on another array with indexOf method

java

sorting

algorithm

lambda

comparator