0

以下代码执行二维矩阵的“分层”排序。首先，它根据 的值对元素进行排序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;
    }
}

使用 Comparator 的代码（不适用于我的情况）：

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);
            }

        }

    };
}
4

1 回答 1

1

您的 Comperator 方法可行，但有一些错误。首先，我会将Doubles替换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

此处还介绍了在保持索引的同时进行排序的第二种方式。归功于 Jon Skeet

于 2013-04-05T13:51:56.977 回答