数组排序，并保持索引

Question

使用Arrays.sort(array);是数组排序一个非常简单的方法。但有一个问题。对于每个未排序的数组，都有一个索引指向某个其他数据结构中的某个对象。在对数组进行排序时（使用上面的代码或任何其他类似的方法），每个值的索引将被更改。是否有解决方案来分配每个值的索引？

EDIT

因为有很多阵列中相同的值的使用HashMap<Key, Value>不会是有用的。

Answer 1

排序两者的数据结构并联。

，或使参考索引（以引用其他数据结构）的每个元素的内部电场，这样每个元件保持相同的“参考索引”，即使各元素的顺序是由排序改变。

或者更好的是，只需给每个元件的内部字段仅仅是一个直接参考变量中的其它数据结构中的元素。 （除非你需要出于某些原因，原始索引本身，而不是只是一个到关联的对象/值reference）

例如：具有在对应的索引与元件中的两个平行阵列this SO Q&A

Answer 2

首先，表示你可能想使用包含两个字段的容器对象将数据结构更改为单个数组。这个容器对象然后将实现Comparable接口。

但是，你所说的坚持，一种方法可能是：

/** 
* Sorts parallel arrays in-place. Sorted by the first array and updating 
* all other arrays to match. 
* Uses the natural sorting of the objects. 
* All arrays must be the same length. 
* 
* @param keys   the values used to sort, may be duplicate 
* 
* @param otherArrays the arrays to have reordered to match the sorting of 
*      the keys array. 
* 
* @exception IllegalArgumentException if any of otherArrays have a length 
*      different that the keys array. 
*/ 
public static <E extends Comparable<? super E>> void sortParallelArrays(
    E[] keys, 
    Object[] ... otherArrays 
) { 
    int numKeys = keys.length; 
    int numOtherArrays = otherArrays.length; 
    for(Object[] otherArray : otherArrays) { 
     if(otherArray.length != numKeys) { 
      throw new IllegalArgumentException("Mismatched array lengths"); 
     } 
    } 
    // A list of all indexes per key 
    // This also does the sorting within the TreeMap using natural ordering 
    SortedMap<E, List<Integer>> originalIndexesByKey = new TreeMap<E, List<Integer>>(); 

    // Populate the map 
    for(int i = 0; i < numKeys; i++) { 
     E key = keys[i]; 
     List<Integer> originalIndexes = originalIndexesByKey.get(key); 
     if(originalIndexes == null) { 
      // Optimization for the non-duplicate keys 
      originalIndexesByKey.put(key, Collections.singletonList(i)); 
     } else { 
      if(originalIndexes.size() == 1) { 
       // Upgrade to ArrayList now that know have duplicate keys 
       originalIndexes = new ArrayList<Integer>(originalIndexes); 
       originalIndexesByKey.put(key, originalIndexes); 
      } 
      originalIndexes.add(i); 
     } 
    } 

    // Store back to keys and sort other arrays in a single traversal 
    Object[][] sortedOtherArrays = new Object[numOtherArrays][numKeys]; 
    int pos = 0; 
    for(Map.Entry<E, List<Integer>> entry : originalIndexesByKey.entrySet()) { 
     E key = entry.getKey(); 
     for(int index : entry.getValue()) { 
      keys[pos] = key; 
      for(int ooIndex = 0; ooIndex < numOtherArrays; ooIndex++) { 
       sortedOtherArrays[ooIndex][pos] = otherArrays[ooIndex][index]; 
      } 
      pos++; 
     } 
    } 
    assert pos == numKeys : "Arrays should be full"; 

    // Copy back to original arrays for in-place sort 
    for(int ooIndex = 0; ooIndex < numOtherArrays; ooIndex++) { 
     System.arraycopy(
      sortedOtherArrays[ooIndex], 0, 
      otherArrays[ooIndex], 0, 
      numKeys); 
    } 
} 

这不是最高效存储策略，但没有太大的代码。

的时间复杂度是不是太糟糕。看起来像O((M+1)*N*log(N))，其中M是其他数组的数量，而N是键的数量。至少没有疯狂的最坏情况问题。