在 Java 中对匹配的数组进行排序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/112234/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Sorting matched arrays in Java
提问by user16773
Let's say that I have two arrays (in Java),
假设我有两个数组（在 Java 中），
int[] numbers; and int[] colors;
int[] 数字；和 int[] 颜色；
Each ith element of numbers corresponds to its ith element in colors. Ex, numbers = {4,2,1} colors = {0x11, 0x24, 0x01}; Means that number 4 is color 0x11, number 2 is 0x24, etc.
数字的每个第 i 个元素对应于它的第 i 个元素的颜色。例如，数字 = {4,2,1} 颜色 = {0x11, 0x24, 0x01}; 表示数字 4 是颜色 0x11，数字 2 是 0x24，等等。
I want to sort the numbers array, but then still have it so each element matches up with its pair in colors.
我想对数字数组进行排序，但仍然保留它，以便每个元素与其颜色对匹配。
Ex. numbers = {1,2,4}; colors = {0x01,0x24,0x11};
前任。数字 = {1,2,4}; 颜色 = {0x01,0x24,0x11};
What's the cleanest, simplest way to do this? The arrays have a few thousand items, so being in place would be best, but not required. Would it make sense to do an Arrays.sort() and a custom comparator? Using library functions as much as possible is preferable.
最干净、最简单的方法是什么？阵列有几千个项目，因此最好放置在适当的位置，但不是必需的。做一个 Arrays.sort() 和一个自定义比较器有意义吗？尽可能多地使用库函数是可取的。
Note: I know the "best" solution is to make a class for the two elements and use a custom comparator. This question is meant to ask people for the quickest way to code this. Imagine being at a programming competition, you wouldn't want to be making all these extra classes, anonymous classes for the comparator, etc. Better yet, forget Java; how would you code it in C?
注意：我知道“最佳”解决方案是为两个元素创建一个类并使用自定义比较器。这个问题旨在询问人们以最快的方式对此进行编码。想象一下，在参加编程比赛时，您不会想要制作所有这些额外的类、比较器的匿名类等。更好的是，忘记 Java；你会如何用 C 编写它？
回答by tovare
You could use sort() with a custom comparator if you kept a third array with the index, and sorted on that, leaving the data intact.
如果您保留带有索引的第三个数组并对其进行排序，则可以将 sort() 与自定义比较器一起使用，从而使数据保持不变。
Java code example:
Java代码示例：
Integer[] idx = new Integer[numbers.length];
for( int i = 0 ; i < idx.length; i++ ) idx[i] = i;
Arrays.sort(idx, new Comparator<Integer>() {
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
Note that you have to use Integerinstead of intor you can't use a custom comparator.
请注意，您必须使用Integer而不是int或不能使用自定义比较器。
回答by Frank Pape
It seems like the cleanest thing to do would be to create a custom property class that implements Comparable. For example:
看起来最干净的方法是创建一个实现 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;
}
}
}
Then you can separate your sorting algorithm from the ordering logic (you could use Collections.sort if you use a List instead of an array), and most importantly, you won't have to worry about somehow getting two arrays out of sync.
然后，您可以将排序算法与排序逻辑分开（如果您使用 List 而不是数组，则可以使用 Collections.sort ），最重要的是，您不必担心以某种方式使两个数组不同步。
回答by finrod
If you'd be willing to allocate some extra space, you could generate another array, call it extra, with elements like this:
如果你愿意分配一些额外的空间，你可以生成另一个数组，称之为额外的，元素如下：
extra = [0,1,...,numbers.length-1]
Then you could sort this extra array using Arrays.sort() with custom comparator (that, while comparing elements i and j really compares numbers[extra[i]] and numbers[extra[j]]). This way after sorting the extra array, extra[0] would contain the index of the smallest number and, as numbers and colours didn't move, the corresponding colour.
This isn't very nice, but it gets the job done, and I can't really think of an easier way to do it.
然后，您可以使用 Arrays.sort() 和自定义比较器对这个额外的数组进行排序（即，在比较元素 i 和 j 时，实际上比较的是 numbers[extra[i]] 和 numbers[extra[j]]）。这样在对 extra 数组进行排序后， extra[0] 将包含最小数字的索引，并且由于数字和颜色没有移动，因此包含相应的颜色。
这不是很好，但它完成了工作，我真的想不出更简单的方法来做到这一点。
As a side note, in the competition I usually find the C++ templated pairs and nice maps indispensable ;)
作为旁注，在比赛中我通常发现 C++ 模板对和漂亮的地图是必不可少的 ;)
回答by Paul Tomblin
I like @tovare's solution. Make a pointer array:
我喜欢@tovare 的解决方案。制作一个指针数组：
int ptr[] = { 1, 2, 3 };
and then when you sort on numbers, swap the values in ptr instead of in numbers. Then access through the ptr array, like
然后当你对数字进行排序时，交换 ptr 中的值而不是数字。然后通过 ptr 数组访问，比如
for (int i = 0; i < ptr.length; i++)
{
printf("%d %d\n", numbers[ptr[i]], colors[ptr[i]]);
}
Update: ok, it appears others have beaten me to this. No XP for me.
更新：好的，看来其他人已经打败了我。对我来说没有 XP。
回答by tovare
An example illustrating using a third index array. Not sure if this is the best implementation.
说明使用第三个索引数组的示例。不确定这是否是最好的实现。
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<sortOrder.length;i++){
System.out.printf("%x %d %d\n",
i,numbers[sortOrder[i]],colors[sortOrder[i]]);
}
}
public static void main(String[] args) {
final Integer[] numbers = {1,4,3,4,2,6};
final Integer[] colors = {0x50,0x34,0x00,0xfe,0xff,0xff};
Integer[] sortOrder = new Integer[numbers.length];
// Create index array.
for(int i=0; i<sortOrder.length; i++){
sortOrder[i] = i;
}
printTable("\nNot sorted",numbers, colors, sortOrder);
Arrays.sort(sortOrder,new Comparator<Integer>() {
public int compare(Integer a, Integer b){
return numbers[b]-numbers[a];
}});
printTable("\nSorted by numbers",numbers, colors, sortOrder);
Arrays.sort(sortOrder,new Comparator<Integer>() {
public int compare(Integer a, Integer b){
return colors[b]-colors[a];
}});
printTable("\nSorted by colors",numbers, colors, sortOrder);
}
}
The output should look like this:
输出应如下所示：
Not sorted No Num Color ---------------- 0 1 80 1 4 52 2 3 0 3 4 254 4 2 255 5 6 255 Sorted by numbers No Num Color ---------------- 0 6 255 1 4 52 2 4 254 3 3 0 4 2 255 5 1 80 Sorted by colors No Num Color ---------------- 0 6 255 1 2 255 2 4 254 3 1 80 4 4 52 5 3 0
回答by JeffFoster
Why not introduce an object to represent a number and a color and implement a comparator function for that?
为什么不引入一个对象来表示一个数字和一个颜色并为此实现一个比较器功能呢？
Also, do you really need an array, why not use something derived from Collection?
另外，你真的需要一个数组，为什么不使用从 Collection 派生的东西？
回答by theycallhimtom
One quick hack would be to combine the two arrays with bit shifts. Make an array of longs such that the most significant 32 bits is the number and the least significant 32 is the color. Use a sorting method and then unpack.
一个快速的技巧是将两个数组与位移相结合。制作一个长数组，其中最高有效的 32 位是数字，最低有效的 32 位是颜色。使用排序方法，然后解包。
回答by Zach Scrivena
Would it suffice to code your own sort method? A simple bubblesort would probably be quick to code (and get right). No need for extra classes or comparators.
编写自己的排序方法就足够了吗？一个简单的冒泡排序可能会很快编码（并且正确）。不需要额外的类或比较器。
回答by kevinarpe
Credit to @tovarefor the original best answer.
归功于@tovare最初的最佳答案。
My answer below removes the (now) unnecessary autoboxing via Maven dependency {net.mintern : primitive : 1.2.2}from this answer: https://stackoverflow.com/a/27095994/257299
我在下面的答案通过 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
回答by Tung Ha
I guess you want performance optimization while trying to avoid using array of objects (which can cause a painful GC event). Unfortunately there's no general solution, thought. But, for your specific case, in which numbers are different from each others, there might be two arrays to be created only.
我猜您在尝试避免使用对象数组（这可能会导致痛苦的 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];
}
}
Two sorted arrays can be replace by Int2IntOpenHashMap, which performs faster run, but memory usage could be double.
两个排序的数组可以用Int2IntOpenHashMap替换，它的运行速度更快，但内存使用量可能翻倍。
