24

Let's say that I have two arrays (in Java),

int[] numbers; and int[] colors;

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 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};

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.

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?

4

13 回答 13

20

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.

Java code example:

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 Integer instead of int or you can't use a custom comparator.

于 2008-09-21T21:43:49.307 回答
8

It seems like the cleanest thing to do would be to create a custom property class that implements Comparable. For example:

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.

于 2008-09-21T21:40:27.503 回答
4

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.

As a side note, in the competition I usually find the C++ templated pairs and nice maps indispensable ;)

于 2008-09-21T21:42:15.627 回答
3

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?

于 2008-09-21T21:34:02.510 回答
3

我喜欢@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。

于 2008-09-21T21:58:27.243 回答
3

说明使用第三个索引数组的示例。不确定这是否是最好的实现。



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

输出应如下所示：

未排序
没有数字颜色
----------------
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
于 2008-09-22T23:44:16.137 回答
2

一种快速的技巧是将两个数组与位移结合起来。制作一个 long 数组，使最高有效 32 位是数字，最低有效 32 位是颜色。使用排序方法，然后打开包装。

于 2008-09-21T22:24:38.583 回答
1

编写自己的排序方法就足够了吗？一个简单的冒泡排序可能会很快编码（并且正确）。不需要额外的类或比较器。

于 2008-09-21T22:03:41.910 回答
1

归功于@tovare原始的最佳答案。

我在下面的答案从这个答案中删除了（现在）通过 Maven 依赖{net.mintern : original : 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
于 2016-04-18T11:24:39.373 回答
1

我想您希望在尝试避免使用对象数组（这可能导致痛苦的 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代替，它运行得更快，但内存使用量可能翻倍。

于 2017-08-04T09:41:11.927 回答
0

You need to sort the colors array by its relative item in the numbers array. Specify a comparator that compares numbers and use that as the comparison for the colors array.

于 2008-09-21T21:32:19.223 回答
0

在 C 中执行此操作的最简单方法是冒泡排序 + 双指针。当然最快的是快速排序+两个指针。当然，第二个指针保持两个数组之间的相关性。

我宁愿将存储在两个数组中的值定义为结构，并在单个数组中使用该结构。然后对它使用快速排序。您可以通过调用比较函数来编写通用版本的排序，然后可以为每个结构编写该函数，但是您已经知道了:)

于 2008-09-22T00:40:47.460 回答
0

使用树形图

于 2010-09-13T09:44:11.643 回答