基於一行數據對二維數組進行排序

Question

我不確定標題是否正確地表明瞭我想要問的內容。比方說，我有如下二維int數組：

int[][] x={{1,7,6},{2,4,8}}; 

現在我想按升序排列的第一行進行排序和數據於第2行必須在排序後的同一列，即後排序，陣列應該是這樣的：

x={{1,6,7},{2,8,4}} 

什麼是正確的方法來做到這一點？

Answer 1

這可以通過實現自己的排序例程來完成，但更好的方法是重構。

嘗試將數據封裝爲數組對，每對數組包含在它自己的對象中。然後，您可以對第一個值進行排序並訪問任一值。

class Pair<T extends Comparable<T>> implements Comparable<Pair<T>> { 
    final T a; 
    final T b; 

    public Pair (T a, T b) { 
    this.a = a; 
    this.b = b; 
    } 

    @Override 
    public int compareTo(Pair<T> o) { 
    // Comparison on 'a' only. 
    return a.compareTo(o.a); 
    } 

    @Override 
    public String toString() { 
    return "{" + a + "," + b + "}"; 
    } 
} 

public static void main(String args[]) { 
    Pair[] pairs = { 
    new Pair(1,2), 
    new Pair(7,4), 
    new Pair(6,8), 
    }; 
    System.out.println("Before: "+Arrays.toString(pairs)); 
    Arrays.sort(pairs); 
    System.out.println("After: "+Arrays.toString(pairs)); 
} 

打印

Before: [{1,2}, {7,4}, {6,8}] 
After: [{1,2}, {6,8}, {7,4}] 

Answer 2

最簡單的方法是創建一個Pair對象持有的對，對的集合與定製的比較，只有比較一對中的第一項進行排序。

如果需要，您可以隨時將對變換回二維數組。

這可能不是最有效的方式，但對於大多數使用情況應該足夠好。

Answer 3

可以通過實現自己的排序算法並將值移動到第二行來完成。你可能有一個Obejcts數組。每個對象將保持值。然後實現您的自定義比較器並使用排序功能。

我還有一個想法：重新排列數組（如果可以的話）。然後將對保存在一個int []表中。而外部表是INT表一conatiner：

int [][] a = {{2,5},{1,4},{3,6}}; 
Arrays.sort(a, new Comparator<int[]>() { 
     @Override 
     public int compare(int[] p_o1, int[] p_o2) { 
      return Integer.valueOf(p_o1[0]).compareTo(p_o2[0]); 
     } 
}); 

Answer 4

如果所有的第一行的元素是獨一無二的，非空，你可以在排序前，填充一個地圖，第一行元素指向其第二排同行。在對第一行進行排序之後，可以使用該映射查找第二行的第一個（排序的）行的相應元素。

Answer 5

你基本上在做一個Map，爲什麼不使用Map實現來幫助你？

TreeMap實現SortedMap，這樣一個簡單的解決辦法是將所有的映射值裏面：

SortedMap<Integer, Integer> map = new TreeMap<Integer, Integer>(); 
map.put(1, 2); 
map.put(7, 4); 
map.put(6, 8); 

// You can iterate over map now, it'll be already sorted 
for(Map.Entry<Integer, Integer> entry: map.entrySet()) 
{ 
    System.out.println(entry.getKey()+" : "+entry.getValue()); 
} 

// This is not really necessary 
Integer[][] x = {map.keySet().toArray(new Integer[0]), map.values().toArray(new Integer[0])}; 

// If you have Apache Commons you can: 
int[][] y = {ArrayUtils.toPrimitive(map.keySet().toArray(new Integer[0])), ArrayUtils.toPrimitive(map.values().toArray(new Integer[0]))}; 

Answer 6

我複製從http://www.algolist.net/Algorithms/Sorting/Quicksort，並稍加修改

public static void main(String[] args) throws Exception { 
     int[][] x = { { 1, 7, 6 }, { 2, 4, 8 } }; 
     qsort(x[0], x[1], 0, x[0].length - 1); 
     System.out.println(Arrays.deepToString(x)); 
    } 

    static void qsort(int[] x0, int[] x1, int left, int right) { 
     int index = partition(x0, x1, left, right); 
     if (left < index - 1) 
      qsort(x0, x1, left, index - 1); 
     if (index < right) 
      qsort(x0, x1, index, right); 
    } 

    static int partition(int[] x0, int[] x1, int left, int right) { 
     int i = left, j = right; 
     int tmp; 
     int pivot = x0[(left + right)/2]; 
     while (i <= j) { 
      while (x0[i] < pivot) 
       i++; 
      while (x0[j] > pivot) 
       j--; 
      if (i <= j) { 
       tmp = x0[i]; 
       x0[i] = x0[j]; 
       x0[j] = tmp; 

       // swap x1 too 
       tmp = x1[i]; 
       x1[i] = x1[j]; 
       x1[j] = tmp; 

       i++; 
       j--; 
      } 
     } 
     return i; 
    } 
} 

這個程序打印粘貼的qsort

[[1, 6, 7], [2, 8, 4]] 

這可能看起來很長，但通常對於算法來說效率非常關鍵，而且這種解決方案似乎是最快的