同时“在适当位置”对多个阵列进行排序 [英] Sort multiple arrays simultaneously "in place"

问题描述

我有以下3个数组：

int[] indexes = new int[]{0,2,8,5};
String[] sources = new String[]{"how", "are", "today", "you"};
String[] targets = new String[]{"I", "am", "thanks", "fine"};

我想根据索引对三个数组进行排序：

I want to sort the three arrays based on the indexes:

indexes -> {0,2,5,8}
sources -> {"how", "are", "you", "today"}
targets -> {"I", "am",  "fine",  "thanks"}

我可以创建一个包含所有三个元素的新类 myClass ：

I can create a new class myClass with all three elements:

class myClass {
    int x;
    String source;
    String target;
}

将所有内容重新分配给myClass，然后排序 myClass 使用 x 。但是，这需要额外的空间。我想知道是否有可能到位排序？谢谢！

Reassign everything to myClass, then sort myClass using x. However, this would required additional spaces. I am wondering if it is possible to do in place sorting? Thanks!

推荐答案

三种方法

1。使用Comparator（需要Java 8 plus）

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 plus）

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]

这篇关于同时“在适当位置”对多个阵列进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！