我有以下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，然后使用 进行排序。但是，这将需要额外的空间。我想知道是否可以进行排序？谢谢！myClassxin place
三种方法
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 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]
这是可能的，尽管它并不像看起来那么容易。有两个选项：
编写自己的排序算法，其中两个元素的交换函数也会交换其他数组中的元素。
AFAIK 没有办法以交换其他数组的方式扩展标准。Array.sort
使用具有排序顺序的帮助程序数组。
首先，您需要使用范围初始化帮助程序数组。{0, 1 ... indexes.Length-1}
现在，您可以使用 与 进行比较而不是与 进行比较的帮助程序数组进行排序。结果是一个帮助器数组，其中每个元素都有其内容应来自的源数组元素的索引，即排序序列。Comparatorindexes[a]indexes[b]ab
最后一步是最棘手的一步。您需要根据上面的排序顺序交换源数组中的元素。
要严格就地操作，请将当前索引设置为 。
然后从帮助程序数组中获取 -th 元素。让我们称之为.这是完成后应放置在索引处的元素索引。
现在，您需要在索引处留出空间，以便将索引中的元素放置在那里。将它们复制到临时位置 。
现在将元素从索引移动到索引 。索引现在可以自由覆盖。
将索引处的帮助器数组中的元素设置为某个无效值，例如 。
将当前索引设置为从上面继续，直到到达帮助程序数组中已经具有无效索引值的元素，即起点。在本例中，存储最后一个索引处的内容。现在，您已经找到了一个旋转索引的闭环。
不幸的是，可能存在任意数量的此类循环，每个循环的大小都是任意大小的。因此，您需要在帮助器数组中查找下一个非无效索引值，然后再次从上面继续，直到处理完帮助程序数组的所有元素。由于您将在每个循环之后的起点结束，因此除非您找到非无效条目，否则递增就足够了。因此，在处理帮助程序数组时，算法仍然是 O（n）。循环完成后，之前的所有条目都必然无效。
如果增量超过帮助程序数组的大小，则操作完成。cur0curfromcurcurfromtmpfromcurfromcur-1curfromtmpcurcurcur
当允许您创建新的目标数组时，选项 2 的变体更简单。
在这种情况下，您只需分配新的目标数组，并根据帮助程序数组中的索引填充其内容。
缺点是，如果数组真的很大，则分配可能非常昂贵。当然，它不再存在。
一些进一步的注意事项。
通常，自定义排序算法的性能更好，因为它避免了临时数组的分配。但在某些情况下，情况会发生变化。循环元素旋转循环的处理使用最小移动操作。这是常见排序算法的 O（n） 而不是 O（n log n）。因此，当要排序的数组数量和/或数组大小增加时，方法 #2 具有优势，因为它使用的交换操作较少。
需要此类排序算法的数据模型大多是设计性的。当然，像往常一样，在一些情况下，您无法避免这种情况。
