Сортируйте несколько массивов одновременно "на месте"

Ответ 1

Три способа сделать это

1. Использование компаратора (требуется Java 8 плюс)

import java.io.*;
import java.util.*;

class Test {

public static String[] sortWithIndex (String[] strArr, int[] intIndex )
    {
     if (! isSorted(intIndex)){
        final List<String> stringList = Arrays.asList(strArr);
        Collections.sort(stringList, Comparator.comparing(s -> intIndex[stringList.indexOf(s)]));
        return stringList.toArray(new String[stringList.size()]);
       }
     else
        return strArr;
    }

public static boolean isSorted(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i + 1] < arr[i]) {
            return false;
        };
    }
    return true;
}       


// Driver program to test function.
    public static void main(String args[])
    {
        int[] indexes = new int[]{0,2,8,5};
        String[] sources = new String[]{"how", "are", "today", "you"};
        String[] targets = new String[]{"I", "am", "thanks", "fine"};   
        String[] sortedSources = sortWithIndex(sources,indexes);
        String[] sortedTargets = sortWithIndex(targets,indexes);
        Arrays.sort(indexes);
        System.out.println("Sorted Sources " + Arrays.toString(sortedSources) + " Sorted Targets " + Arrays.toString(sortedTargets)  + " Sorted Indexes " + Arrays.toString(indexes));
    }
}

Выход

Sorted Sources [how, are, you, today] Sorted Targets [I, am, fine, thanks] Sorted Indexes [0, 2, 5, 8]

2. Использование Lambda (требуется Java 8 плюс)

import java.io.*;
import java.util.*;

public class Test {

public static String[] sortWithIndex (String[] strArr, int[] intIndex )
    {

  if (! isSorted(intIndex)) {
        final List<String> stringList = Arrays.asList(strArr);
        Collections.sort(stringList, (left, right) -> intIndex[stringList.indexOf(left)] - intIndex[stringList.indexOf(right)]);
        return stringList.toArray(new String[stringList.size()]);
  }
  else 
    return strArr;
    }

public static boolean isSorted(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i + 1] < arr[i]) {
            return false;
        };
    }
    return true;
}  

// Driver program to test function.
public static void main(String args[])
{
    int[] indexes = new int[]{0,2,5,8};
    String[] sources = new String[]{"how", "are", "today", "you"};
    String[] targets = new String[]{"I", "am", "thanks", "fine"};   
    String[] sortedSources = sortWithIndex(sources,indexes);
    String[] sortedTargets = sortWithIndex(targets,indexes);
    Arrays.sort(indexes);
    System.out.println("Sorted Sources " + Arrays.toString(sortedSources) + " Sorted Targets " + Arrays.toString(sortedTargets)  + " Sorted Indexes " + Arrays.toString(indexes));
}

}

3. Использование списков и карт и избежание множественных вызовов (как во втором решении выше) методу сортировки отдельных массивов

import java.util.*;
import java.lang.*;
import java.io.*;

public class Test{

    public static <T extends Comparable<T>> void sortWithIndex( final List<T> key, List<?>... lists){
        // input validation
        if(key == null || lists == null)
            throw new NullPointerException("Key cannot be null.");

        for(List<?> list : lists)
            if(list.size() != key.size())
                throw new IllegalArgumentException("All lists should be of the same size");

        // Lists are size 0 or 1, nothing to sort
        if(key.size() < 2)
            return;

        // Create a List of indices
        List<Integer> indices = new ArrayList<Integer>();
        for(int i = 0; i < key.size(); i++)
            indices.add(i);

        // Sort the indices list based on the key
        Collections.sort(indices, new Comparator<Integer>(){
            @Override public int compare(Integer i, Integer j) {
                return key.get(i).compareTo(key.get(j));
            }
        });

        Map<Integer, Integer> swapMap = new HashMap<Integer, Integer>(indices.size());
        List<Integer> swapFrom = new ArrayList<Integer>(indices.size()),
                      swapTo   = new ArrayList<Integer>(indices.size());

        // create a mapping that allows sorting of the List by N swaps.
        for(int i = 0; i < key.size(); i++){
            int k = indices.get(i);
            while(i != k && swapMap.containsKey(k))
                k = swapMap.get(k);

            swapFrom.add(i);
            swapTo.add(k);
            swapMap.put(i, k);
        }

        // use the swap order to sort each list by swapping elements
        for(List<?> list : lists)
            for(int i = 0; i < list.size(); i++)
                Collections.swap(list, swapFrom.get(i), swapTo.get(i));
    }

    public static void main (String[] args) throws java.lang.Exception{

      List<Integer> index = Arrays.asList(0,2,8,5);
      List<String> sources = Arrays.asList("how", "are", "today", "you");
      // List Types do not need to be the same
      List<String> targets  = Arrays.asList("I", "am", "thanks", "fine");

      sortWithIndex(index, index, sources, targets);

      System.out.println("Sorted Sources " + sources + " Sorted Targets " + targets  + " Sorted Indexes " + index);


    }
}

Выход

Sorted Sources [how, are, you, today] Sorted Targets [I, am, fine, thanks] Sorted Indexes [0, 2, 5, 8]

Ответ 2

Это возможно, хотя это не так просто, как кажется. Существует два варианта:

1. напишите свой собственный алгоритм сортировки, где функция подкачки для двух элементов также меняет местами в других массивах.

   AFAIK нет возможности расширить стандартный массив Array.sort таким образом, чтобы он менял дополнительные массивы.

2. Используйте вспомогательный массив с порядком сортировки.

   • Прежде всего вам нужно инициализировать вспомогательный массив с диапазоном {0, 1... indexes.Length-1}.

   • Теперь вы сортируете вспомогательный массив с помощью Comparator который сравнивает indexes[a] с indexes[b] а не с a по b. Результатом является вспомогательный массив, в котором каждый элемент имеет индекс элемента исходного массива, из которого должно поступать его содержимое, т.е. Последовательность сортировки.

   • Последний шаг - самый сложный. Вам необходимо поменять элементы в исходных массивах в соответствии с порядком сортировки выше.
     Для того, чтобы работать строго на месте установить текущий индекс cur к 0.
     Затем возьмите элемент cur -th из вашего вспомогательного массива. Пусть называют его from. Это индекс элемента, который должен быть помещен в index cur после завершения.
     Теперь вам нужно, чтобы освободить место на указательный cur поместить элементы из индекса from там. Скопируйте их во временное местоположение tmp.
     Теперь переместите элементы из индекса from индекса в cur. Индекс from теперь можно свободно переопределить.
     Установите элемент в вспомогательном массиве с индексом cur на некоторое недопустимое значение, например -1.
     Установите текущий индекс cur, чтобы from проследовать сверху, пока не достигнете элемента в массиве хелперов, который уже имеет недопустимое значение индекса, т.е. начальную точку. В этом случае сохраните содержимое tmp по последнему индексу. Теперь вы нашли замкнутый цикл с повернутыми индексами.
     К сожалению, может существовать произвольное число таких циклов каждого из произвольных размеров. Поэтому вам нужно искать в вспомогательном массиве для следующего недействительного значения индекса и снова продолжать сверху, пока не будут обработаны все элементы вспомогательного массива. Поскольку вы закончите в начальной точке после каждого цикла, достаточно cur если вы не найдете недействительную запись. Таким образом, алгоритм остается O (n) при обработке вспомогательного массива. Все записи перед cur обязательно недействительны после завершения цикла.
     Если cur увеличивается больше размера вспомогательного массива, вы закончите.

3. Существует более легкое изменение варианта 2, когда вам разрешено создавать новые целевые массивы.
   В этом случае вы просто выделяете новые целевые массивы и заполняете их содержимое в соответствии с индексами в вашем вспомогательном массиве.
   Недостатком является то, что распределения могут быть довольно дорогими, если массивы действительно велики. И, конечно, его больше нет.

Некоторые дополнительные заметки.

• Обычно алгоритм пользовательской сортировки работает лучше, поскольку он позволяет избежать выделения временного массива. Но в некоторых случаях ситуация меняется. Обработка циклов вращения циклического элемента использует операции минимального перемещения. Это O (n), а не O (n log n) общих алгоритмов сортировки. Поэтому, когда количество массивов для сортировки и/или размера массивов растет, метод №2 имеет преимущество, поскольку он использует меньше операций свопинга.

• Модель данных, требующая такого алгоритма сортировки, как правило, нарушается по дизайну. Конечно, как всегда, есть несколько случаев, когда вы не можете этого избежать.

Ответ 3

Могу ли я предложить вам использовать TreeMap или что-то подобное, используя ваше целое в качестве ключа.

static Map<Integer, myClass> map = new TreeMap<>();

Поэтому, когда вы хотите получить заказ, вам нужно сделать цикл for или что угодно.

for (int i : map.keyset()){
    System.out.println("x: "+map.get(i).x+"\nsource: "+map.get(i).source+"\ntarget: "+map.get(i).target);
}

Ответ 4

В этом примере требуется создать массив индексов Integer, но массивы, подлежащие сортировке, переупорядочиваются на месте в соответствии с массивом1, а массивы могут быть любого типа (примитивы или объекты), которые позволяют индексировать.

public static void main(String[] args) {
    int array1[]={5,1,9,3,8}; 
    int array2[]={2,0,3,6,1};
    int array3[]={3,1,4,5,9};
    // generate array of indices
    Integer[] I = new Integer [array1.length];
    for(int i = 0; i < I.length; i++)
        I[i] = i;
    // sort array of indices according to array1
    Arrays.sort(I, (i, j) -> array1[i]-array1[j]);
    // reorder array1 ... array3 in place using sorted indices
    // also reorder indices back to 0 to length-1
    // time complexity is O(n)
    for(int i = 0; i < I.length; i++){
        if(i != I[i]){
            int t1 = array1[i];
            int t2 = array2[i];
            int t3 = array3[i];
            int j;
            int k = i;
            while(i != (j = I[k])){
                array1[k] = array1[j];
                array2[k] = array2[j];
                array3[k] = array3[j];
                I[k] = k;
                k = j;
            }
            array1[k] = t1;
            array2[k] = t2;
            array3[k] = t3;
            I[k] = k;
        }
    }
    // display result
    for (int i = 0; i < array1.length; i++) {
        System.out.println("array1 " + array1[i] +
           " array2 " + array2[i] +
           " array3 " + array3[i]);
    }
}

Ответ 5

Другое решение, использующее Collection (увеличение использования памяти):

Пусть создать отсортированную карту будет просто отображение между правильным индексом и исходной позицией:

public static TreeMap<Integer, Integer> sortIndex(int[] array){
    TreeMap<Integer, Integer> tree = new TreeMap<>();
    for(int i=0; i < array.length; ++i) {
        tree.put(array[i], i);
    }   
    return tree;
}

Тестовое задание:

int[] indexes = new int[] { 0, 1, 3, 2, 4, 5 };
TreeMap<Integer, Integer> map = sortIndex(indexes);

map.keySet().stream().forEach(System.out::print); //012345
map.values().stream().forEach(System.out::print); //013245

У нас отсортированы индексы (по ключу) и исходный индексный порядок как значения.

Нет, мы можем просто использовать это, чтобы упорядочить массив, я буду радикальным и использую Stream для сопоставления и сбора в List.

public static List<String> sortInPlace(String[] array, TreeMap<Integer, Integer> map) {
    return map.values().stream().map(i -> array[i]).collect(Collectors.toList());
}

Тестовое задание:

String[] sources = "to be not or to be".split(" ");

int[] indexes = new int[] { 0, 1, 3, 2, 4, 5 };
TreeMap<Integer, Integer> map = sortIndex(indexes);

List<String> result = sortInPlace(sources, map);
System.out.println(result);

[быть или не быть]

Почему я использовал List. В основном, чтобы упростить переупорядочение, если мы попытаемся заказать оригинальные массивы, это будет сложно, потому что нам нужно удалить противоположный ключ/пару

2 -> 3
3 -> 2

Без некоторой очистки мы просто поменяем ячейки дважды... так что изменений не будет.

Если мы хотим немного сократить использование памяти, мы можем создать другой массив вместо использования потока и скопировать значения для значений, повторяющих карту. Это также можно было бы сделать с несколькими массивами параллельно.

Ответ 6

Все зависит от размера ваших массивов. Это решение будет использовать первый массив для выполнения сортировки, но будет выполнять перестановку на нескольких массивах.
Таким образом, это может иметь некоторые проблемы с производительностью, если для используемого алгоритма сортировки потребуется много перестановок.

Здесь я взял базовый алгоритм сортировки, на котором я добавил некоторые действия, которые я могу сделать во время замены двух ячеек. Это позволяет использовать некоторые лямбды для обмена несколькими массивами одновременно на основе одного массива.

public static void sortArray( int[] array, BiConsumer<Integer, Integer>... actions ) {
    int tmp;
    for ( int i = 0, length = array.length; i < length; ++i ) {
        tmp = array[i];
        for ( int j = i + 1; j < length; ++j ) {
            if ( tmp > array[j] ) {
                array[i] = array[j];
                array[j] = tmp;
                tmp = array[i];

                // Swap the other arrays
                for ( BiConsumer<Integer, Integer> cons : actions ){
                    cons.accept( i,  j);
                }
            }
        }
    }
}

Позвольте создать общий метод для замены ячеек, которые мы можем передать в виде BiConsumer lambda (работает только для не примитивных массивов):

public static <T> void swapCell( T[] array, int from, int to ) {
    T tmp = array[from];
    array[from] = array[to];
    array[to] = tmp;
}

Это позволяет использовать для сортировки массивы типа:

public static void main( String[] args ) throws ParseException {
    int[] indexes = new int[] { 0, 2, 8, 5 };
    String[] sources = new String[] { "how", "are", "today", "you" };
    String[] targets = new String[] { "I", "am", "thanks", "fine" };

    sortArray( indexes,
            ( i, j ) -> swapCell( sources, i, j ),
            ( i, j ) -> swapCell( targets, i, j ) );

    System.out.println( Arrays.toString( indexes ) );
    System.out.println( Arrays.toString( sources ) );
    System.out.println( Arrays.toString( targets ) );
}

[0, 2, 5, 8]
[как у вас сегодня дела]
[Я в порядке, спасибо]

Это решение не требует (много) больше памяти, чем тот, который уже использовался, поскольку не требуется дополнительный массив или Collection.

Использование BiConsumer<>... обеспечивает общее решение, это также может принять Object[]... но это больше не будет работать для массива примитивов. Конечно, это небольшая потеря производительности, поэтому, исходя из необходимости, это можно удалить.

Создавая полное решение, сначала определим интерфейс, который будет использоваться как завод:

interface Sorter {
    void sort(int[] array, BiConsumer<Integer, Integer>... actions);

    static void sortArrays(int[] array, BiConsumer<Integer, Integer>... actions){
        // call the implemented Sorter
    }
}

Затем выполните простой сортировщик выбора с той же логикой, что и раньше, для каждой перестановки в исходном массиве мы выполняем BiConsumer:

class SelectionSorter implements Sorter {
    public void sort(int[] array, BiConsumer<Integer, Integer>... actions) {
        int index;
        int value;
        int tmp;
        for (int i = 0, length = array.length; i < length; ++i) {
            index = i;
            value = array[i];
            for (int j = i + 1; j < length; ++j) {
                if (value > array[j]) {
                    index = j;
                    value = array[j];
                }
            }

            if (index != i) {
                tmp = array[i];
                array[i] = array[index];
                array[index] = tmp;

                // Swap the other arrays
                for (BiConsumer<Integer, Integer> cons : actions) {
                    cons.accept(i, index);
                }
            }
        }
    }
}

Позвольте также создать сортировщик Bubble:

class BubbleSorter implements Sorter {
    public void sort(int[] array, BiConsumer<Integer, Integer>... actions) {
        int tmp;

        boolean swapped;
        do {
            swapped = false;
            for (int i = 1, length = array.length; i < length; ++i) {
                if (array[i - 1] > array[i]) {
                    tmp = array[i];
                    array[i] = array[i - 1];
                    array[i - 1] = tmp;

                    // Swap the other arrays
                    for (BiConsumer<Integer, Integer> cons : actions) {
                        cons.accept(i, i - 1);
                    }

                    swapped = true;
                }
            }
        } while (swapped);
    }
}

Теперь мы можем просто называть одно или другое на основе простого условия: длина:

static void sortArrays(int[] array, BiConsumer<Integer, Integer>... actions){
    if(array.length < 1000){
        new BubbleSorter().sort(array, actions);
    } else {
        new SelectionSorter().sort(array, actions);
    }
}

Таким образом, мы можем вызвать нашего сортировщика просто с помощью

Sorter.sortArrays(indexes, 
    (i, j) -> swapCell(sources, i, j), 
    (i, j) -> swapCell(targets, i, j)
);

Полный тестовый пример на идеоне (ограничение по размеру из-за тайм-аута)

Ответ 7

Интересно, действительно ли мой подход.

    public class rakesh{

    public static void sort_myClass(myClass myClasses[]){
        for(int i=0; i<myClasses.length; i++){
            for(int j=0; j<myClasses.length-i-1; j++){
                if(myClasses[j].x >myClasses[j+1].x){
                    myClass temp_myClass = new myClass(myClasses[j+1]);
                    myClasses[j+1] = new myClass(myClasses[j]);
                    myClasses[j] = new myClass(temp_myClass);
                }
            }
        }
    }

    public static class myClass{
        int x;
        String source;
        String target;
        myClass(int x,String source,String target){
          this.x = x;
          this.source = source;
          this.target = target;
        }
        myClass(myClass super_myClass){
            this.x = super_myClass.x;
            this.source = super_myClass.source;
            this.target = super_myClass.target;
        }
    }

    public static void main(String args[]) {
        myClass myClass1 = new myClass(0,"how","I");
        myClass myClass2 = new myClass(2,"are","am");
        myClass myClass3 = new myClass(8,"today","thanks");
        myClass myClass4 = new myClass(5,"you","fine");
        myClass[] myClasses = {myClass1, myClass2, myClass3, myClass4};

        sort_myClass(myClasses);

        for(myClass myClass_dummy : myClasses){
            System.out.print(myClass_dummy.x + " ");
        }
        System.out.print("\n");
        for(myClass myClass_dummy : myClasses){
            System.out.print(myClass_dummy.source + " ");
        }
        System.out.print("\n");
        for(myClass myClass_dummy : myClasses){
            System.out.print(myClass_dummy.target + " ");
        }
    }


}

Если вы обнаружите какую-либо ошибку или имеете предложения, пожалуйста, оставьте комментарий, чтобы я мог внести необходимые изменения.

Выход

0 2 5 8
как у вас сегодня дела
я в порядке, спасибо
Процесс завершен с кодом выхода 0

Ответ 8

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

    Integer[] indexes = new Integer[]{0,2,8,5};
    String[] sources = new String[]{"how", "are", "today", "you"};
    String[] targets = new String[]{"I", "am", "thanks", "fine"};
    Integer[] sortedArrya = Arrays.copyOf(indexes, indexes.length);
    Arrays.sort(sortedArrya);
    String[] sortedSourses = new String[sources.length];
    String[] sortedTargets = new String[targets.length];
    for (int i = 0; i < sortedArrya.length; i++) {
        int intValus = sortedArrya[i];
        int inx = Arrays.asList(indexes).indexOf(intValus);
        sortedSourses[i] = sources[+inx];
        sortedTargets[i] = targets[+inx];
    }
    System.out.println(sortedArrya);
    System.out.println(sortedSourses);
    System.out.println(sortedTargets);

Ответ 9

У меня есть другое решение для вашего вопроса:

private void reOrder(int[] indexes, String[] sources, String[] targets){
        int[] reIndexs = new int[indexes.length]; // contain index of item from MIN to MAX
        String[] reSources = new String[indexes.length]; // array sources after re-order follow reIndexs
        String[] reTargets = new String[indexes.length]; // array targets after re-order follow reIndexs
        for (int i=0; i < (indexes.length - 1); i++){
            if (i == (indexes.length - 2)){
                if (indexes[i] > indexes[i+1]){
                    reIndexs[i] = i+1;
                    reIndexs[i+1] = i;
                }else
                {
                    reIndexs[i] = i;
                    reIndexs[i+1] = i+1;
                }
            }else
            {
                for (int j=(i+1); j < indexes.length; j++){
                    if (indexes[i] > indexes[j]){
                        reIndexs[i] = j;
                    }else {
                        reIndexs[i] = i;
                    }
                }
            }
        }

        // Re-order sources array and targets array
        for (int index = 0; index < reIndexs.length; index++){
            reSources[index] = sources[reIndexs[index]];
            reTargets[index] = targets[reIndexs[index]];
        }

        // Print to view result
        System.out.println( Arrays.toString(reIndexs));
        System.out.println( Arrays.toString(reSources));
        System.out.println( Arrays.toString(reTargets));
    }

Ответ 10

Вы также можете добиться своего.

Здесь я создал ArrayList myArr и отсортировал его по значению индекса, а затем преобразовал обратно в массив, если вы удовлетворены ArrayList, просто вы можете удалить преобразование или хотите, чтобы этот массив был полезным.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class StackOverflow {
    public static void main(String[] args) {
        int[] indexes = new int[]{0,2,8,5};
        String[] sources = new String[]{"how", "are", "today", "you"};
        String[] targets = new String[]{"I", "am", "thanks", "fine"};
        ArrayList<myClass> myArr=new ArrayList<>();
        for(int i=0;i<indexes.length;i++) {
            myArr.add(new myClass(indexes[i], sources[i], targets[i]));
        }
        //Collections.sort(myArr,new compareIndex()); 
        // Just for readability of code 
        Collections.sort(myArr, (mC1, mC2) -> mC1.getX() - mC2.getX());

       //Conversion Part
       for (int i=0;i<myArr.size();i++){
           indexes[i]=myArr.get(i).getX();
           sources[i]=myArr.get(i).getSource();
           targets[i]=myArr.get(i).getTarget();
       }

        System.out.println(Arrays.toString(indexes));
        System.out.println(Arrays.toString(sources));
        System.out.println(Arrays.toString(targets));

    }
}
class myClass {
    private Integer x;
    private String source;
    private String target;
    public myClass(Integer x,String source,String target){
        this.x=x;
        this.source=source;
        this.target=target;
    }

    public Integer getX() {
        return x;
    }

    public String getSource() {
        return source;
    }

    public String getTarget() {
        return target;
    }
}