Сортировка совпадающих массивов в Java

Вам нужно отсортировать массив цветов по его относительному элементу в массиве чисел. Укажите компаратор, который сравнивает числа, и используйте его как сравнение для массива цветов.

Почему бы не ввести объект для представления числа и цвета и не реализовать для этого функцию компаратора?

Кроме того, вам действительно нужен массив, почему бы не использовать что-то производное от Collection?

Кажется, что проще всего было бы создать собственный класс свойств, реализующий 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;
    }
  }
}

Затем вы можете отделить свой алгоритм сортировки от логики упорядочения (вы можете использовать Collections.sort, если вы используете List вместо массива), и, что наиболее важно, вам не придется беспокоиться о том, чтобы каким-то образом рассинхронизировать два массива.

Если вы хотите выделить дополнительное пространство, вы можете сгенерировать другой массив, назовите его extra, с такими элементами:

extra = [0,1,...,numbers.length-1]

Затем вы можете отсортировать этот дополнительный массив, используя Arrays.sort () с настраиваемым компаратором (который при сравнении элементов i и j действительно сравнивает числа [extra [i]] и числа [extra [j]]). Таким образом, после сортировки дополнительного массива extra [0] будет содержать индекс наименьшего числа и, поскольку числа и цвета не перемещаются, соответствующий цвет. Это не очень хорошо, но работа выполняется, и я не могу придумать более простого способа сделать это.

Кстати, на соревнованиях я обычно считаю, что пары шаблонов 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<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

Обратите внимание, что вам нужно использовать Integer вместо int, иначе вы не можете использовать собственный компаратор.

Мне нравится решение @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.

Достаточно ли написать собственный метод сортировки? Простая пузырьковая сортировка, вероятно, будет быстро закодирована (и будет правильной). Нет необходимости в дополнительных классах или компараторах.

Один из быстрых способов - объединить два массива с помощью битовых сдвигов. Составьте массив длинных чисел так, чтобы 32 старших бита были числом, а младшие 32 - цветом. Воспользуйтесь методом сортировки, а затем распакуйте.

Самый простой способ сделать это в C - это пузырьковая сортировка + двойные указатели. Конечно, самым быстрым будет быстрая сортировка + два указателя. Конечно, второй указатель поддерживает корреляцию между двумя массивами.

Я бы предпочел определить значения, которые хранятся в двух массивах, как структуру и использовать структуру в одном массиве. Затем используйте быструю сортировку. вы можете написать общую версию сортировки, вызвав функцию сравнения, которая затем может быть написана для каждой структуры, но тогда вы уже знаете это :)

Пример, иллюстрирующий использование третьего массива индексов. Не уверен, что это лучшая реализация.

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

Результат должен выглядеть так:

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

Используйте TreeMap

Благодарим @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, который выполняет более быстрый запуск, но использование памяти может быть удвоено.