同时对多个arrays进行排序“就地”

我有以下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，然后使用x对myClass进行排序。 但是，这需要额外的空间。 我想知道是否可以进行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 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 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 > void sortWithIndex( final List 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 indices = new ArrayList(); for(int i = 0; i < key.size(); i++) indices.add(i); // Sort the indices list based on the key Collections.sort(indices, new Comparator(){ @Override public int compare(Integer i, Integer j) { return key.get(i).compareTo(key.get(j)); } }); Map swapMap = new HashMap(indices.size()); List swapFrom = new ArrayList(indices.size()), swapTo = new ArrayList(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 index = Arrays.asList(0,2,8,5); List sources = Arrays.asList("how", "are", "today", "you"); // List Types do not need to be the same List 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 对辅助数组进行排序，该Comparator将indexes[a]与indexes[b]而不是a到b 。 结果是一个辅助数组，其中每个元素都有源数组元素的索引，其内容应该来自，即排序顺序。

   • 最后一步是最棘手的一步。 您需要根据上面的排序顺序交换源数组中的元素 。
     要严格操作，请将当前索引cur设置为0 。
     然后从辅助数组中获取cur -th元素。 我们来吧。 这是完成后应放在index cur的元素索引。
     现在你需要在索引cur处创建空间以from那里放置索引元素。 将它们复制到临时位置tmp 。
     现在将元素从索引移到索引cur 。 现在可以自由地覆盖索引。
     将索引cur处的辅助数组中的元素设置为某个无效值，例如-1 。
     将当前索引cur设置from从上面继续，直到到达辅助数组中已经具有无效索引值（即起始点）的元素。 在这种情况下，将tmp的内容存储在最后一个索引处。 您现在已经找到了旋转索引的闭环。
     不幸的是，可能存在任意数量的这种循环，每个循环具有任意大小。 因此，您需要在辅助数组中寻找下一个非无效索引值，并再次从上面继续，直到处理辅助数组的所有元素。 由于您将在每个循环后的起始点结束，因此除非您找到非无效条目，否则增加cur就足够了。 因此，在处理辅助数组时，算法仍然是O（n）。 在完成循环之后， cur之前的所有条目必然无效。
     如果cur增量超出辅助数组的大小，则完成。

3. 当您被允许创建新的目标数组时，选项2有一个更容易的变化。
   在这种情况下，您只需分配新的目标数组并根据辅助数组中的索引填充其内容。
   缺点是如果arrays非常大，分配可能会非常昂贵。 当然，它已经不复存在了 。

---

进一步说明。

• 通常，自定义排序算法执行得更好，因为它避免了临时数组的分配。 但在某些情况下情况会发生变化。 循环元素旋转循环的处理使用最小移动操作 。 这是常见排序算法的O（n）而不是O（n log n）。 因此，当要排序的数组的数量和/或数组的大小增加时，方法＃2具有优势，因为它使用较少的交换操作。

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

Answer 3

我建议您使用TreeMap或类似的东西，使用整数作为键。

 static Map 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); } 

Answer 4

此示例需要创建一个Integer索引数组，但要排序的数组将根据array1重新排序，并且数组可以是允许索引的任何类型（基元或对象）。

 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]); } } 

Answer 5

使用Collection另一种解决方案（增加内存使用量）：

让我们创建一个有序映射，它只是正确索引和原始位置之间的映射：

 public static TreeMap sortIndex(int[] array){ TreeMap 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 map = sortIndex(indexes); map.keySet().stream().forEach(System.out::print); //012345 map.values().stream().forEach(System.out::print); //013245 

我们将索引（在键上）和原始索引顺序作为值排序。

不，我们可以简单地使用它来订购数组，我会非常激动并使用Stream来映射并收集到List 。

 public static List sortInPlace(String[] array, TreeMap 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 map = sortIndex(indexes); List result = sortInPlace(sources, map); System.out.println(result); 

[生存还是毁灭]

为什么我使用List 。 主要是为了简化重新排序，如果我们尝试订购原始数组，它将很复杂，因为我们需要删除相反的键/对

 2 -> 3 3 -> 2 

如果没有一些清洁，我们将只交换两次细胞......所以不会有任何变化。

如果我们想减少一点内存使用量，我们可以创建另一个数组，而不是使用流和复制迭代地图的每个值的值。 这也可以并行处理多个数组。

Answer 6

这一切都取决于arrays的大小。 此解决方案将使用第一个数组执行排序，但将在多个数组上执行排列。
因此，如果使用的排序算法需要大量的排列，这可能会有一些性能问题。

在这里，我采用了一种基本的排序算法，我在其中添加了一些在两个单元格交换期间可以执行的操作。 这允许使用定义一些lambda来基于一个数组同时交换多个数组。

 public static void sortArray( int[] array, BiConsumer... 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 cons : actions ){ cons.accept( i, j); } } } } } 

让我们创建一个通用方法来交换我们可以作为BiConsumer lambda传递的单元格（仅适用于非基本数组）：

 public static  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]
[你今天好吗]
[我很好，谢谢]

此解决方案不需要（多）内存比已使用的内存更多，因为不需要额外的arrays或Collection 。

使用BiConsumer<>...提供了一个通用的解决方案，这也可以接受一个Object[]...但是这对于原始数组不再有效。 当然，这会有轻微的性能损失，因此根据需要，可以将其删除。

---

创建一个完整的解决方案，首先让我们定义一个将用作工厂的接口：

 interface Sorter { void sort(int[] array, BiConsumer... actions); static void sortArrays(int[] array, BiConsumer... actions){ // call the implemented Sorter } } 

然后，使用与以前相同的逻辑实现一个简单的Selection sorterr，对于原始数组中的每个排列，我们执行BiConsumer ：

 class SelectionSorter implements Sorter { public void sort(int[] array, BiConsumer... 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 cons : actions) { cons.accept(i, index); } } } } } 

还要创建一个冒泡分拣机：

 class BubbleSorter implements Sorter { public void sort(int[] array, BiConsumer... 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 cons : actions) { cons.accept(i, i - 1); } swapped = true; } } } while (swapped); } } 

现在，我们可以根据一个简单的条件简单地调用一个或另一个，长度：

 static void sortArrays(int[] array, BiConsumer... 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) ); 

关于ideone的完整测试用例（由于超时而限制了大小）

Answer 7

我想知道我的方法是否有效。

  public class rakesh{ public static void sort_myClass(myClass myClasses[]){ for(int i=0; imyClasses[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结束

Answer 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); 

Answer 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)); } 

Answer 10

你也可以用自己的方式实现。

在这里，我创建了一个ArrayList myArr并根据索引值进行排序，然后如果您对ArrayList满意，则将其转换回数组，只是您可以删除转换，或者您希望Array对此有所帮助。

 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 myArr=new ArrayList<>(); for(int i=0;i mC1.getX() - mC2.getX()); //Conversion Part for (int i=0;i