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

Question

Предположим, что у меня есть два массива (на Java),

int [] numbers; и int [] цвета;

Каждый i-й элемент чисел соответствует его i-му элементу в цветах. Ex, numbers = {4,2,1} colors = {0x11, 0x24, 0x01}; Значит, что номер 4 является цветом 0x11, номер 2 равен 0x24 и т. Д.

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

Ex. numbers = {1,2,4}; colors = {0x01,0x24,0x11};

Какой самый чистый и простой способ сделать это? Массивы имеют несколько тысяч предметов, поэтому быть на месте лучше, но не требуется. Имеет ли смысл делать массив Arrays.sort() и пользовательский компаратор? Предпочтительно использовать библиотечные функции.

Примечание: Я знаю, что «лучшим» решением является создание класса для двух элементов и использование пользовательского компаратора. Этот вопрос предназначен для того, чтобы попросить людей как можно быстрее закодировать это. Представьте, что вы участвуете в конкурсе на программирование, вы не хотели бы делать все эти дополнительные классы, анонимные классы для компаратора и т. Д. Еще лучше забыть Java; как бы вы закодировали его в C?

Answer 1

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

Answer 2

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

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

Answer 3

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

Answer 4

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

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

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

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

Answer 5

Вы можете использовать сортировки() с пользовательским компаратором, если вы сохранили третий массив с индексом, и отсортированы по этому, оставив данные неповрежденными.

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

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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

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

Answer 10

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

 
    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 

Answer 11

Использовать TreeMap

Answer 12

Кредит @tovare для оригинального лучшего ответа.

Мой ответ ниже удаляет (сейчас) ненужную Autoboxing через 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 

Answer 13

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