在Java中对匹配的数组进行排序
假设我有两个数组（在Java中），
int []数字; 和int []颜色;
数字的每个第i个元素对应于颜色中的第i个元素。 例如，数字= {4,2,1}颜色= {0x11,0x24,0x01}; 意味着数字4是颜色0x11，数字2是0x24等。
我想对数字数组进行排序，但仍然有它，所以每个元素都与颜色对匹配。
防爆。 数字= {1,2,4}; colors = {0x01,0x24,0x11};
什么是最干净，最简单的方法？ arrays有几千个项目，因此最好，但不是必需的。 做一个Arrays.sort（）和自定义比较器是否有意义？ 最好使用库函数。
注意：我知道“最佳”解决方案是为两个元素创建一个类并使用自定义比较器。 这个问题的目的是要求人们以最快的方式对此进行编码。 想象一下参加一个编程竞赛，你不会想要制作所有这些额外的类，比较器的匿名类等等。更好的是，忘记Java; 你会怎么用C编码呢？
如果保留带索引的第三个数组，则可以将sort（）与自定义比较器一起使用，并对其进行排序，使数据保持不变。
Java代码示例：
Integer[] idx = new Integer[numbers.length]; for( int i = 0 ; i < idx.length; i++ ) idx[i] = i; Arrays.sort(idx, new Comparator() { public int compare(Integer i1, Integer i2) { return Double.compare(numbers[i1], numbers[i2]); } }); // numbers[idx[i]] is the sorted number at index i // colors[idx[i]] is the sorted color at index i 请注意，您必须使用Integer而不是int否则您无法使用自定义比较器。
看起来最干净的事情似乎是创建一个实现Comparable的自定义属性类。 例如：
class Color implements Comparable { private int number; private int color; // (snip ctor, setters, etc.) public int getNumber() { return number; } public int getColor() { return color; } public int compareTo(Color other) { if (this.getNumber() == other.getNumber) { return 0; } else if (this.getNumber() > other.getNumber) { return 1; } else { return -1; } } }
然后，您可以将排序算法与排序逻辑分开（如果使用List而不是数组，则可以使用Collections.sort），最重要的是，您不必担心以某种方式使两个数组不同步。
如果你愿意分配一些额外的空间，你可以使用这样的元素生成另一个数组，称之为额外的数组：
extra = [0,1,...,numbers.length-1]
然后你可以使用Arrays.sort（）和自定义比较器对这个额外的数组进行排序（虽然比较元素i和j确实比较数字[extra [i]]和数字[extra [j]]）。 这种方式在对额外数组进行排序后，extra [0]将包含最小数字的索引，并且由于数字和颜色未移动，因此将包含相应的颜色。
这不是很好，但它完成了工作，我真的不能想到一个更简单的方法。
作为旁注，在竞赛中我通常会发现C ++模板对和漂亮的地图不可或缺;）
为什么不引入一个对象来表示数字和颜色，并为此实现比较器function？
另外，你真的需要一个数组，为什么不使用从Collection派生的东西？
我喜欢@ tovare的解决方案。 创建一个指针数组：
int ptr[] = { 1, 2, 3 };
然后当你对数字排序时，交换ptr中的值而不是数字。 然后通过ptr数组访问，就像
for (int i = 0; i < ptr.length; i++) { printf("%d %d\n", numbers[ptr[i]], colors[ptr[i]]); }
更新：好吧，似乎其他人已经打败了我。 没有XP对我来说。
示例使用第三索引数组的示例。 不确定这是否是最好的实现。
import java.util。*;
public class Sort { private static void printTable(String caption, Integer[] numbers, Integer[] colors, Integer[] sortOrder){ System.out.println(caption+ "\nNo Num Color"+ "\n----------------"); for(int i=0;i() { public int compare(Integer a, Integer b){ return numbers[b]-numbers[a]; }}); printTable("\nSorted by numbers",numbers, colors, sortOrder); Arrays.sort(sortOrder,new Comparator() { public int compare(Integer a, Integer b){ return colors[b]-colors[a]; }}); printTable("\nSorted by colors",numbers, colors, sortOrder); } }
输出应如下所示：
没有排序 没有颜色 ---------------- 0 1 80 1 4 52 2 3 0 3 4 254 4 2 255 5 6 255 按数字排序 没有颜色 ---------------- 0 6 255 1 4 52 2 4 254 3 3 0 4 2 255 5 1 80 按颜色排序 没有颜色 ---------------- 0 6 255 1 2 255 2 4 254 3 1 80 4 4 52 5 3 0
一个快速的黑客就是将两个arrays与位移组合在一起。 创建一个long数组，使得最重要的32位是数字，最不重要的32是颜色。 使用排序方法然后解压缩。
编码自己的排序方法是否足够？ 一个简单的bubbleort可能会很快编码（并且正确）。 无需额外的课程或比较。
@tovare获得最佳答案。
我的回答从这个答案中删除了（现在）不必要的自动装箱，通过Maven依赖{net.mintern：primitive：1.2.2} ： https ：//stackoverflow.com/a/27095994/257299
int[] idx = new int[numbers.length]; for( int i = 0 ; i < idx.length; i++ ) idx[i] = i; final boolean isStableSort = false; Primitive.sort(idx, (i1, i2) -> Double.compare(numbers[i1], numbers[i2]), isStableSort); // numbers[idx[i]] is the sorted number at index i // colors[idx[i]] is the sorted color at index i
我想你希望在尝试避免使用对象数组时进行性能优化（这会导致痛苦的GC事件）。 不幸的是，没有一般的解决方案。 但是，对于您的特定情况，其中数字彼此不同，可能只有两个数组可以创建。
/** * work only for array of different numbers */ private void sortPairArray(int[] numbers, int[] colors) { int[] tmpNumbers = Arrays.copyOf(numbers, numbers.length); int[] tmpColors = Arrays.copyOf(colors, colors.length); Arrays.sort(numbers); for (int i = 0; i < tmpNumbers.length; i++) { int number = tmpNumbers[i]; int index = Arrays.binarySearch(numbers, number); // surely this will be found colors[index] = tmpColors[i]; } }
两个排序的数组可以由Int2IntOpenHashMap替换，它可以执行更快的运行，但内存使用量可能会增加一倍。
您需要按数字数组中的相对项对颜色数组进行排序。 指定比较数字的比较器，并将其用作colors数组的比较。
在C中执行此操作的最简单方法是bubblesort + dual指针。 当然，最快的是快速排名+两个指针。 当然，第二个指针保持两个数组之间的相关性。
我宁愿将存储在两个数组中的值定义为结构，并在单个数组中使用该结构。 然后在上面使用quicksort。 你可以通过调用一个比较函数编写一个通用版本的sort，然后可以为每个结构编写，但是你已经知道:)
使用TreeMap