同时对多个阵列进行排序"就地"

Question

我有以下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"};

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

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

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

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

将所有内容重新分配给myClass,然后myClass使用排序x.但是,这需要额外的空间.我想知道是否可以进行in place排序？谢谢!

Answer 1

这样做的三种方式

1.使用比较器(需要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]

Answer 2

它有可能虽然它不像看起来那么容易.有两种选择:

1. 编写自己的排序算法,其中两个元素的交换函数也交换其他数组中的元素.

   AFAIK无法以Array.sort交换其他阵列的方式扩展标准.

2. 使用具有排序顺序的辅助数组.

   • 首先,您需要使用范围初始化辅助数组{0, 1 ... indexes.Length-1}.

   • 现在你排序辅助阵列使用Comparator的是比较indexes[a]用indexes[b],而不是a到b.结果是一个辅助数组,其中每个元素都有源数组元素的索引,其内容应该来自,即排序顺序.

   • 最后一步是最棘手的一步.您需要根据上面的排序顺序交换源数组中的元素.
     要严格操作,请将当前索引设置cur为0.
     然后cur从辅助数组中取出-th元素.我们称之为from.这是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具有优势,因为它使用较少的交换操作.

• 需要像这样的排序算法的数据模型大多是设计破坏的.当然,像往常一样,有些情况下你无法避免这种情况.