數組排序，並保持索引

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是鍵的數量。至少沒有瘋狂的最壞情況問題。