基於兩個參數的二維數組排序

Question

以下代碼執行二維矩陣的「分層」排序。首先，它根據ranks的值對元素進行排序。其次，它採用這個排序矩陣，搜索具有相同值ranks的元素，並根據dist對它們進行排序。按降序排列。

問題1：是否有可能以更簡單的方式實現相同的結果？我試圖創建一個Comparator，但它提供了不正確的結果，對於這種特殊情況。

問題2：如何在排序後得到未排序元素的索引？

import java.util.ArrayList; 

public class Test { 

    public static void main(String args[]) { 

     ArrayList<ArrayList<Double>> values = new ArrayList<ArrayList<Double>>(); 

     ArrayList<Double> ranks = new ArrayList<Double>(); 
     ArrayList<Double> dist = new ArrayList<Double>(); 

     ranks.add(8.0); 
     ranks.add(3.0); 
     ranks.add(8.0); 
     ranks.add(1.0); 

     dist.add(1.8); 
     dist.add(2.8); 
     dist.add(1.9); 
     dist.add(2.1); 

     values.add(0,ranks); 
     values.add(1,dist); 

     int len = ranks.size(); 

     ArrayList<ArrayList<Double>> sortedranks = new ArrayList<ArrayList<Double>>(); 

     sortedranks = order(values,0,ranks.size()); 

     boolean swapped = true; 
     int j = 0; 
     double tmp1, tmp2; 
     while (swapped) { 
       swapped = false; 
       j++; 
       for (int i = 0; i < len - j; i++) { 
        double val1 = sortedranks.get(0).get(i); 
        double val2 = sortedranks.get(0).get(i+1); 
        if (val1==val2) { 
        if (sortedranks.get(1).get(i) < sortedranks.get(1).get(i+1)) {  
         tmp1 = sortedranks.get(1).get(i); 
         tmp2 = sortedranks.get(1).get(i+1); 
         sortedranks.get(1).remove(i); 
         sortedranks.get(1).remove(i); 
         sortedranks.get(1).add(i,tmp2); 
         sortedranks.get(1).add(i+1,tmp1); 
         swapped = true; 
        } 
        } 
       }     
     } 

     for (int i = 0; i < len; i++) { 
      System.out.println("Ranks " + i + " : " + sortedranks.get(0).get(i) 
        + ", Distances : " + sortedranks.get(1).get(i)); 
     } 


    } 

    public static ArrayList<ArrayList<Double>> order(ArrayList<ArrayList<Double>> values, int i_start, int i_fin) { 
     boolean swapped = true; 
     int j = 0; 
     int i_rank = 0; 
     int i_dist = 1; 
     double tmp1_rank, tmp2_rank, tmp1_dist, tmp2_dist; 
     while (swapped) { 
       swapped = false; 
       j++; 
       for (int i = i_start; i < i_fin - j; i++) {          
        if (values.get(i_rank).get(i) < values.get(i_rank).get(i+1)) {       
          tmp1_rank = values.get(i_rank).get(i); 
          tmp2_rank = values.get(i_rank).get(i+1); 
          tmp1_dist = values.get(i_dist).get(i); 
          tmp2_dist = values.get(i_dist).get(i+1); 
          values.get(i_rank).remove(i); 
          values.get(i_rank).remove(i); 
          values.get(i_dist).remove(i); 
          values.get(i_dist).remove(i); 
          values.get(i_rank).add(i,tmp2_rank); 
          values.get(i_rank).add(i+1,tmp1_rank); 
          values.get(i_dist).add(i,tmp2_dist); 
          values.get(i_dist).add(i+1,tmp1_dist); 
          swapped = true; 
        } 
       }     
     } 
     return values; 
    } 
} 

使用比較的代碼（不適合我的情況下工作）：

public class MyEntry implements Comparable<MyEntry> { 

    private Double rank; 
    private Double dist; 

    public MyEntry(double rank, double dist) { 

     this.rank = rank; 
     this.dist = dist; 

    } 

    public static Comparator<MyEntry> ValueComparator = new Comparator<MyEntry>() { 

     public int compare(MyEntry value1, MyEntry value2) { 

      Double rfirst = value1.rank; 
      Double rsecond = value2.rank; 

      Double dfirst = value1.dist; 
      Double dsecond = value2.dist; 

      if (rsecond != rfirst) { 
       return (int) (rsecond - rfirst); 
      } 
      else { 
       return (int) (dsecond - dfirst); 
      } 

     } 

    }; 
} 

Answer 1

你Comperator方法是有效的，但有一些錯誤。 首先我會用double替換MyEntry中的Double。

比較Double是不一樣的比較double 例如：

Double a = 1.0; 
Double b = 1.0; 
System.out.println(a == b); 
System.out.println(a.equals(b)); 
System.out.println(a.doubleValue()== b.doubleValue()); 

將返回

false 
true 
true 

然後，在你投以int比較，但是這意味着地板的數據。 (int) (2 - 1.9)會給0 更好的是使用<並返回-1或1

public static Comparator<MyEntry> ValueComparator = new Comparator<MyEntry>() { 

    public int compare(MyEntry value1, MyEntry value2) { 

     double rfirst = value1.rank; 
     double rsecond = value2.rank; 

     double dfirst = value1.dist; 
     double dsecond = value2.dist; 

     if (rsecond != rfirst) { 
      return rsecond < rfirst?-1:1; 
     } 
     else if(dsecond!=dfirst){ 
      return dsecond < dfirst ?-1:1; 
     } 
     return 0; 

    } 
} 

對於您所需要的索引你的第二個問題比較。這可以通過兩種方式完成。第一種選擇是包括MyEntry這樣的指標：

public class MyEntry implements Comparable<MyEntry> { 

private double rank; 
private double dist; 
private int index; 
private static int nextIndex = 0; 

public MyEntry(double rank, double dist) { 

    this.rank = rank; 
    this.dist = dist; 
    this.index = nextIndex++; 

} 

這種方式，您將能夠保留指數，但它不是那麼靈活。

更靈活的方法可能是將索引放在單獨的數組中，然後對其進行排序。

class IndexedArrayComparator implements Comparator<Integer>{ 

    MyEntry[] array; 

    public IndexedArrayComparator(MyEntry[] entries){ 
     this.array=entries; 
    } 

    public Integer[] createIndexes(){ 
     Integer[] index = new Integer[array.length]; 
     for(int i =0;i<index.length;i++){ 
      index[i]=i; 
     } 
     return index; 
    } 

    public int compare(Integer i0, Integer i1) { 
     double rfirst = array[i0].rank; 
     double rsecond = array[i1].rank; 

     double dfirst = array[i0].dist; 
     double dsecond = array[i1].dist; 

     if (rsecond != rfirst) { 
      return rsecond > rfirst?-1:1; 
     } 
     else if(dsecond!=dfirst){ 
      return dsecond > dfirst ?-1:1; 
     } 
     return 0; 
    } 

} 

然後，您可以使用它像這樣：

MyEntry[] entries = new MyEntry[5]; 
entries[0]= new MyEntry(1.1,5); 
entries[1]= new MyEntry(1.1,4); 
entries[2]= new MyEntry(2.1,5); 
entries[3]= new MyEntry(0.1,3); 
entries[4]= new MyEntry(3.1,1); 

IndexedArrayComparator comp = new IndexedArrayComparator(entries); 
Integer[] index = comp.createIndexes(); 
Arrays.sort(index,comp); 
for(int i =0;i<index.length;i++){ 
    MyEntry e = entries[index[i]]; 
    System.out.println(String.format("%2d:r= %3.1f, d= %3.1f" ,index[i],e.rank,e.dist)); 
} 

哪位能給：

3:r= 0.1, d= 3.0 
1:r= 1.1, d= 4.0 
0:r= 1.1, d= 5.0 
2:r= 2.1, d= 5.0 
4:r= 3.1, d= 1.0 

同時保持指數也被描述here排序的第二種方式。積分給Jon Skeet