Preface
When it refers to the comparison operation of comparing the "size" of two objects when performing algorithms such as insertion sort, Hill sort, and merge sort. It is easy to understand the comparison method of integer i>j, but when we sort multiple objects, how do we compare the "size" of two objects? Such comparisons of stu1 > stu2 are obviously impossible to compile. To solve the problem of how to compare the size of two objects, JDK provides two interfaces java.lang.Comparable and java.util.Comparator .
1. Natural sorting: java.lang.Comparable
There is only one method provided in the Comparable interface: compareTo(Object obj) , and the return value of this method is int . If the return value is a positive number, it means that the current object (the object that calls the method) is "larger" than the obj object; otherwise, it is "small"; if it is zero, it means that the two objects are equal.
Here is a Student class that implements the Comparable interface:
public class Student implements Comparable { private int id; private String name; public Student() { super(); } @Override public int compareTo(Object obj) { if (obj instanceof Student) { Student stu = (Student) obj; return id - stu.id; } return 0; } @Override public String toString() { return "<" + id + ", " + name + ">"; } } Student implements the natural sorting interface Comparable. So how do we use this interface to sort a set of Student objects? When we were learning arrays, we used a class to sort the integer arrays: java.util.Arrays . We use Arrays' sort method to sort integer arrays. After flipping through the API documentation, you will find that Arrays gives many overloaded forms of the sort method, including sort(Object[] obj) , which means that Arryas can also sort object arrays. When comparing the "size" of the two objects during the sorting process, the Comparable interface is used to compare the compareTo method.
public class CompareTest { public static void main(String[] args) { Student stu1 = new Student(1, "Little"); Student stu2 = new Student(2, "Cyntin"); Student stu3 = new Student(3, "Tony"); Student stu4 = new Student(4, "Gemini"); Student[] stus = new Student[4]; stu0] = stu1; stu1 [1] = stu4; stus[2] = stu3; stu3] = stu2; System.out.println("Array: " + Arrays.toString(stus)); Arrays.sort(stus); System.out.println("Sort: " + Arrays.toString(stus)); } } The order in which elements are added in the Student array is not added according to the student ID. After calling Arrays.sort(stus) , sort the Student array. No matter which sort algorithm is used to implement it, it is definitely necessary to compare the "size" operation of two objects. So how do you compare the "size" of two objects? The Comparable interface implemented by Student comes into play. The sort method will cast the object to be compared to Comparable and call the compareTo method to judge the "size" of these two objects based on its return value. Therefore, in this example, the original Student out-of-order array sorted becomes a Student array sorted by student number.
But we noticed that the sorting algorithm is bound to the Student class, and Student only has one sorting algorithm. But this is not the case in the real society. What if we don’t want to sort by student number? What if we want to sort students by name? We can only modify the compareTo method of the Comparable interface of the Student class and change it to sort by name. What if there are two operations in the same system, one is sorted by student number and the other is sorted by name? It is impossible to write two compareTo methods implementations in the Student class body. From this point of view, Comparable has limitations. In order to make up for this shortcoming, JDK also provides us with another sorting method, which is the comparator sorting we will talk about below.
2. Comparator sorting: java.util.Comparator
I mentioned above that the reason why the comparator sorting interface is provided is that sometimes it is necessary to sort the same object in many different ways, and this natural sorting Comparable cannot be implemented. In addition, one advantage of the Comparator interface is that it separates the comparison sorting algorithm from the specific entity class.
If you look through the API, you will find that there is also an overloaded form of Arrays.sort: sort(T[] a, Comparator<? super T> c) . The method uses generics to write parameters of this method, which we have not mentioned yet. We can understand it as this form: sort(Object[] a, Comparator c) , which means sorting the Object array according to the comparison sorting algorithm given by comparator c. There are two methods defined in the Comparator interface: compare(Object o1, Object o2) and equals methods. Since the equals method has methods for all objects, when we implement the Comparator interface, we only need to override compare method, instead of override the equals method. The description of overriding equals method in the Comparator interface is: "Note that it is always safe not to overwrite Object.equals(Object) method. However, in some cases, overwriting this method can allow the program to determine whether two different Comparators force the same sorting, thereby improving performance." We only need to know the first sentence and it is OK. That is to say, we don’t have to think about how to implement the equals method, because even if we don’t show the implementation of the equals method, but use the equals method of the Object class, the code is still safe.
So let's write a code to sort it with a comparator. It is still done with the Student class, but the Comparable interface is not implemented. Since the comparator implementation class only uses display to implement one method, we can do not need to write a class to implement it. When we need to use a comparator, we can write an anonymous internal class to implement Comparator.
Here is our method of sorting by name:
public void sortByName () { Student stu1 = new Student(1, "Little"); Student stu2 = new Student(2, "Cyntin"); Student stu3 = new Student(3, "Tony"); Student stu4 = new Student(4, "Gemini"); Student[] stus = new Student[4]; stu0] = stu1; stu1; stu4; stu2] = stu3; stu3] = stu2; System.out.println("Array: " + Arrays.toString(stus)); Arrays.sort(stus, new Comparator() { @Override public int compare(Object o1, Object o2) { if (o1 instanceof Student && o2 instanceof Student) { Student s1 = (Student) o1; Student s2 = (Student) o2; //return s1.getId() - s2.getId(); //arrange by Id return s1.getName().compareTo(s2.getName()); //arrange by name} return 0; } }); System.out.println("Sorted: " + Arrays.toString(stus)); }When we need to sort Student by student number, we just need to modify the code in the inner class that implements Comparator in our sorting method, without modifying the Student class.
Note: Of course, you can also use the Student class to implement the Comparator interface, so that Student is (is a) comparator (Comparator). When you need to use this sort, just use Student as a Comparator. You can pass Student as a parameter into the sort method because Student is a Comparator. But such code is not excellent code, because one of the important reasons why we use comparator is that it can separate the comparison algorithm from specific classes and reduce the coupling between classes.
TreeSet provides support for both comparison methods, corresponding to the two constructor methods of TreeSet:
1. TreeSet(): Comparison and sort according to the compareTo method of the Comparable interface implemented by elements in TreeSet
2. TreeSet(Comparator comparator): Comparison and sort elements in TreeSet according to the given comparator comparator
When adding an element to a TreeSet, the TreeSet sorts the elements. As for whether to sort with natural order or comparator, it depends on how your TreeSet construct is written. Of course, there will be no comparison when adding the first element. There are no elements in the TreeSet. Who can I compare with?
Below, the TreeSet test code using two sorting and comparison methods are given:
/** * Use natural sort* Student must implement the Comparable interface, otherwise ClassCastException will be thrown */ public void testSortedSet3() { Student stu1 = new Student(1, "Little"); Student stu2 = new Student(2, "Cyntin"); Student stu3 = new Student(3, "Tony"); Student stu4 = new Student(4, "Gemini"); SortedSet set = new TreeSet(); set.add(stu1); set.add(stu3); // If Student does not implement the Comparable interface, throw ClassCastException set.add(stu4); set.add(stu2); set.add(stu4); set.add(new Student(12, "Little")); System.out.println(set); } /** * Use comparator to sort* Student can be just a simple Java class without implementing the Comparable interface*/ public void testSortedSet3() { Student stu1 = new Student(1, "Little"); Student stu2 = new Student(2, "Cyntin"); Student stu3 = new Student(3, "Tony"); Student stu4 = new Student(4, "Gemini"); SortedSet set = new TreeSet(new Comparator() { @Override public int compare(Object o1, Object o2) { if (o1 instanceof Student && o2 instanceof Student) { Student s1 = (Student) o1; Student s2 = (Student) o2; return s1.getName().compareTo(s2.getName()); } return 0; } }); set.add(stu1); set.add(stu3); set.add(stu4); set.add(stu2); set.add(stu4); set.add(new Student(12, "Little")); System.out.println(set); } In addition, introduce a tool class, java.util.Collections . Note that this is not a Collection interface. Collections are very similar to the Arrays class. Arrays provides a series of static methods for array operations, find sorting, and more. Collections also provides a series of such methods, but it is used to process collections. Although the Collections class is very similar to the Collections interface, don't be fooled by the name of Collections. It is not an implementation class that can only handle the Collection interface and sub-interfaces, but can also handle the implementation class of the Map interface.
Summarize
This is the end of the introduction to natural sorting and comparator sorting in Java. The article is still relatively detailed. I hope it can help you in your study or work. If you have any questions, you can leave a message to communicate.