问题 比较器/可比较集合类中的升序或降序是什么?


我知道我们可以按照我们的要求对存储在Collection中的对象进行排序或排序。

虽然我得到了深刻的理解,但我并不相信安排的升序和降序是通过(a - b) - >升序或(b - a) - >降序来实现的,其中“a”和“b”是班级我们选择比较的成员。

例:

public int compareTo(Student s) {
     return this.grade - s.grade; //ascending order 
    // return s.grade - this.grade; // descending order
}

订购对象元素背后的逻辑是什么?怎么“(this.grade - s.grade)”如果正1移动“this.grade”前面并按顺序放“s.grade”,为什么不以其他方式?谁验证了比较结果(+ 1,-1,0),然后分别按升序或降序排列,是否有任何文档描述了这部分的内部工作?

public class Student implements Comparable <Student>{
    String name;
    int grade;
    public Student(String name, int grade) {
        this.name = name;
        this.grade = grade;
    }
    public int compareTo(Student s) {
         return this.grade - s.grade; //ascending order 
        // return s.grade - this.grade; // descending order
    }
    public String toString() {
        return this.name + ", " + this.grade;
    }
}

请分享,谢谢!


编辑:

我得到了Java文档,我的问题是这样的:

sort these grades (13, 2)

Case ascending -> return this.grade - s.grade;

picture in my mind: 
compare (13, 2) , (13 - 2) > 0 so move 2 to front.
result -> 2, 13
------
Case descending -> return s.grade - this.grade;

picture in my mind: 
compare (2, 13) , (2 - 13) < 0 so move 13 to front.

result -> 13, 2

“这是怎么发生的?”是我原来的问题。我看过文档,仍然无法弄清楚。


5677
2017-09-29 20:03


起源

你问题的答案取决于你是如何排序的 Student(S)? - Elliott Frisch
@ElliottFrisch,我提到如果升序我需要使用(this.grade - s.grade),但为什么this.grade是第一个,s.grade是第二个,即为什么(s.grade)从(this.grade)中减去)?为什么不通过其他方式? ,这是我需要遵循的标准规则,以使它们按升序排列吗? - David Prun
改变结果 compareTo 没有来电者什么都不做。结果由调用者解释,并在文档中记录 比较 的javadoc。 - Elliott Frisch
你不应该开始减去。当值接近Integer.MAX_VALUE或Integer.MIN_VALUE时,您将最终得到错误的代码。 - aioobe
实现Comparable的每个类都负责定义自己的自然排序顺序。如果调用者想要以相反的顺序对该类的项进行排序,那么他们必须做一些额外的工作。 - Alex


答案:


订购对象元素背后的逻辑是什么?怎么“(this.grade - s.grade)”如果正1移动“this.grade”前面并按顺序放“s.grade”,为什么不以其他方式?

使用负数来表示“这比这个还要小”,正数表示“这不仅仅是”,0表示“这两件事情是平等的”已经在许多计算机语言中使用了30多年。

谁验证了比较结果(+ 1,-1,0),然后分别按升序/降序排列,是否有任何文档描述了这部分的内部工作?

有几个内部类使用返回值来重新排序数组或集合中的元素,包括

Collections.sort() Arrays.sort() TreeSet

编辑

要回答如何工作,您将不得不查看我上面列出的每个类的源代码。其中一些是非常复杂的尝试使排序尽可能高效。但总的来说,这一切都归结为代码如下:

if( data[i].compareTo(data[j]) > 0 ){
   // swap data[i] and  data[j]
}

9
2017-09-29 20:11



谢谢,但我在编辑的帖子中清除了我想要的内容。 - David Prun
@DavidPrun我在答案中添加了更多内容 - dkatzel


@DavidPrun好问题。我试过用一个例子解释这个。

(x,y) - >(2,5)

升序 (则x.compareTo(Y)):

如果x.compareTo(y)== 1,则x> y,因为y小于x,你必须在x前面移动y。

2.compareTo(5)== -1,然后不要在2前面移动5。

降序 (y.compareTo(X)):

如果y.compareTo(x)== 1,则y> x,因为y大于x,你必须在x前面移动y。

5.compareTo(2)== 1,在2前面移动5。

基本上,如果compareTo方法的结果为1,我们将始终在x前面移动y。


3
2018-01-11 06:20





Collections.sort()方法可以。

现在idk究竟是java中sort()的算法是什么,我相信它是一个修改过的双合并排序......但是在那个代码中的某个地方,compareTo(Comparable c)被调用来确定什么是大于/小于,生病尝试解释在一个简单的算法中:

让我说我有圆圈,通常你会比较圆圈的直径所以......

public class Circle implements Comparable<Cricle> {
 int diameter;
 //constructor
 public int compareTo(Circle c){
  return this.diameter-c.diameter;
   }

现在让我们制作一个圆圈阵列:

ArrayList<Circle> collection = new ArrayList;
collection.add(new Circle(10)); // and more circles

现在假设这是Collection.sort()中定义的排序算法:

  Comparable tmp;
  for(int i=0;i<collection.size();i++){
   for(int j=i;j<collection.size();j++){
    if(collection.get(j).compareTo(collection.get(i)>0){
      //swap
      tmp=collection.get(i);
      collection.set(i,collection.get(j));
      collection.set(j,tmp);
     }
    }
   }

现在我不确定我写的排序算法写(升/降)我刚刚做得很快,但我想这一点很明显,排序()是如何决定什么在哪里...你可以在评论中提出进一步的解释


1
2017-09-29 20:19



你接近理解我的问题,谢谢。 - David Prun