在Java中同时对三个ArrayList进行排序的最有效方法是什么？

Question

我有三个ArrayLists，其中一个是字符串names，另外两个是整数score和picture numbers。我想按照玩家的得分（从高到低）同时对它们进行排序。现在我使用了简单的冒泡排序，但是当Lists变得更大时，我认为这种方法不会很有效。

这是我的代码：

public class MyBubbleSort {

    public static void bubble_srt(List<Integer> score, List<String> name, List<Integer> pic) {
        int n = score.size();
        int k;
        for (int m = n; m >= 0; m--) {
            for (int i = 0; i < n - 1; i++) {
                k = i + 1;
                if (score.get(i) < score.get(k)) {
                    swapNumbers(i, k, score, name, pic);
                }
            }
            printNumbers(score);
        }
    }

    private static void swapNumbers(int i, int j, List<Integer> score, List<String> name, List<Integer> pic) {

        int temp;
        temp = score.get(i);
        score.set(i, score.get(j));
        score.set(j, temp);

        String s;
        s = name.get(i);
        name.set(i, name.get(j));
        name.set(j, s);

        int p;
        p = pic.get(i);
        pic.set(i, pic.get(j));
        pic.set(j, p);

    }

    private static void printNumbers(List<Integer> input) {

        for (int i = 0; i < input.size(); i++) {
            System.out.print(input.get(i) + ", ");
        }
        System.out.print("\n");
    }

}

谢谢！

- Gidi Sprintzin

Answer 1

最好的方法是创建一个包含得分、名称和图片属性的类，并使用该类的单个列表进行排序，您可以使用 Collections.sort 和根据分数属性比较两个实例的 Comparator 进行排序。

与其他排序算法（归并排序、快速排序）相比，冒泡排序效率低下。而且没有必要自己实现排序算法，因为标准的Java包已经为您实现了这一点。

- Eran

Answer 2

首先创建一个名为PlayerInfo的类，如下所示：

package test;

public class PlayerInfo {

    private String name;
    private Integer score;
    private Integer pictureId;

    public PlayerInfo(final String name, final Integer score, final Integer pictureId) {
        this.name = name;
        this.score = score;
        this.pictureId = pictureId;
    }

    public String getName() {
        return this.name;
    }

    public void setName(final String name) {
        this.name = name;
    }

    public Integer getScore() {
        return this.score;
    }

    public void setScore(final Integer score) {
        this.score = score;
    }

    public Integer getPictureId() {
        return this.pictureId;
    }

    public void setPictureId(final Integer pictureId) {
        this.pictureId = pictureId;
    }

    @Override
    public String toString() {
        return this.name + ":" + this.score + ":" + this.pictureId;
    }
}

第二步是创建一个 PlayerInfo Comparator。这里我们创建了一个 ScoreBasedComparator（根据您的要求，但您也可以创建其他比较器以适应特定需求）：

package test;

import java.util.Comparator;

public class ScoreBasedComparator implements Comparator<PlayerInfo> {

    @Override
    public int compare(final PlayerInfo playerInfo1, final PlayerInfo playerInfo2) {
        return playerInfo1.getScore().compareTo(playerInfo2.getScore());
    }

}

最后，您可以通过以下方式对 List 中的 PlayerInfo 实例进行排序：Collections.sort(<要排序的集合>, <自定义的比较器>)

package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Runner {

    public static void main(final String[] args) {
        List<PlayerInfo> playerInfos = new ArrayList<PlayerInfo>();
        playerInfos.add(new PlayerInfo("A", 123, 1));
        playerInfos.add(new PlayerInfo("B", 1, 2));
        playerInfos.add(new PlayerInfo("C", 23, 3));
        playerInfos.add(new PlayerInfo("D", 300, 4));
        Collections.sort(playerInfos, new ScoreBasedComparator());
        System.out.println(Arrays.toString(playerInfos.toArray()));
    }

}

运行这个小程序将会输出以下内容：

[B:1:2, C:23:3, A:123:1, D:300:4]

正如您所看到的，您的集合在创建时是未排序的，但按照得分排序后打印出来。

希望这可以帮助您。

- Kraal

Answer 3

如果目标是根据其中一个数组对三个数组进行排序，而不将这些数组合并为一个常规类，则可以创建一个索引数组（0到size-1），然后根据其中一个数组对索引数组进行排序（使用内置的排序和自定义比较）。然后根据排序后的索引数组重新排序所有三个数组。我不知道 Java 是否有内置的重新排序函数。以下是按照索引数组 I 对 A、B 和 C 三个数组进行重新排序的 C 示例，时间复杂度为 O(n)（线性，每个存储位置都将值放在其排序位置）。最后将 I 恢复为 0 到 n-1。

    // reorder A,B,C in place according to I
    // tA,tB,tC are temps
    for(i = 0; i < n; i++){
        if(i != I[i]){
            tA = A[i];
            tB = B[i];
            tC = C[i];
            k = i;
            while(i != (j = I[k])){
                A[k] = A[j];
                B[k] = B[j];
                C[k] = C[j];
                I[k] = k;
                k = j;
            }
            A[k] = tA;
            B[k] = tB;
            C[k] = tC;
            I[k] = k;
        }
    }

- rcgldr