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

Ответ 1

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

Ответ 2

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

Ответ 3

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

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

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

В качестве побочного примечания, в конкурсе я обычно нахожу, что С++-шаблонные пары и приятные карты незаменимы;)

Ответ 4

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

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

Ответ 5

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

Ответ 6

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

    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

Ответ 7

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

Ответ 8

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

Ответ 9

Подтвердите @tovare за исходный лучший ответ.

Мой ответ ниже удаляет (теперь) ненужное автобоксирование через зависимость от Maven {net.mintern: primitive: 1.2.2} из этого ответа: fooobar.com/questions/125536/...

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

Ответ 10

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

Ответ 11

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

Ответ 12

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

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

Ответ 13

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