It is often necessary to sort lists, from List<String> to sort custom classes. No need to merge or heap sort on your own. Just implement one interface.
This article will first introduce the use of Collections to sort List<String> , and then talk about the principle of Collections.sort.
Let’s talk about how to sort custom classes.
Finally , another method of sorting custom objects using Collections sort will be introduced, and the two sorts are simple performance comparison.
1. The principle of sorting List<String> and Collections.sort
The code is as follows
List<String> stringList = new ArrayList<String>(); stringList.add("nice"); stringList.add("delicious"); stringList.add("able"); stringList.add("moon"); stringList.add("try"); stringList.add("friend"); Collections.sort(stringList); for (String str : stringList) { System.out.println(str); }Where Collections are java.util.Collections.
Check out the sort implementation in Collections
@SuppressWarnings("unchecked") public static <T extends Comparable<? super T>> void sort(List<T> list) { Object[] array = list.toArray(); Arrays.sort(array); int i = 0; ListIterator<T> it = list.listIterator(); while (it.hasNext()) { it.next(); it.set((T) array[i++]); } }From this we can see that the sorting body is Arrays.sort(array); the sort implementation of Arrays is
public static void sort(Object[] array) { // BEGIN android-changed ComparableTimSort.sort(array); // END android-changed }Continue to track, ComparableTimSort's sort implementation ComparableTimSort.sort
static void sort(Object[] a) to static void sort(Object[] a, int lo, int hi) to private static void binarySort(Object[] a, int lo, int hi, int start). In binarySort, the part used for size comparison is
Comparable<Object> pivot = (Comparable) a[start]; int left = lo; int right = start; assert left <= right; while (left < right) { int mid = (left + right) >>> 1; if (pivot.compareTo(a[mid]) < 0) right = mid; else left = mid + 1; }The compareTo of Object will be called for comparison. By default, both String and Integer types have been overridden by the compareTo method. So you can compare it yourself
2. Comparison of custom classes
Through the above introduction, we understand the principle of Collections sorting. The following is to introduce the sorting of custom objects. First, check the comparison principle of Integer and String, and then introduce how to compare custom classes.
2.1 We checked the implementation of Object and found that there is no compareTo method.
Look at the Integer definition
public final class Integer extends Number implements Comparable<Integer>
Let's look at the definition of String
public final class String implements java.io.Serializable, Comparable<String>, CharSequence
We can find that they all inherit from Comparable
2.2 View Comparable interface
You can find that there is only one method in Comparable
Java code
public int compareTo(T o);
In other words, the binarySort method actually calls the Comparable compareTo method, so as to know that as long as it is inherited from Comparable,
And implement compareTo to call Collections.sort to sort custom objects
2.3 Comparison of custom classes
The following code is to sort the User. First, sort by name one by one. If the names are the same, sort from small to large by age.
Java code
public class MainTest { public static void main(String[] args) { List<User> userList = new ArrayList<User>(); userList.add(new User("Lucy", 19)); userList.add(new User("Jack", 19)); userList.add(new User("Jim", 19)); userList.add(new User("James", 19)); userList.add(new User("Herry", 19)); userList.add(new User("Luccy", 19)); userList.add(new User("James", 18)); userList.add(new User("Herry", 20)); Collections.sort(userList); for (User user : userList) { System.out.println(user.getName() + "/t/t" + user.getAge()); } } private static class User implements Comparable<User> { private String name; private int age; public User(String name, int age) { this.name = name; this.age = age; } @Override public int compareTo(User another) { int compareName = this.name.compareTo(another.getName()); if (compareName == 0) { return (this.age == another.getAge() ? 0 : (this.age > another.getAge() ? 1 : -1)); } return compareName; } public String getName() { return name; } public int getAge() { return age; } } }After execution, the output is:
Xml code:
Herry 19 Herry 20 Jack 19 James 18 James 19 Jim 19 Luccy 19 Lucy 19
It can be seen that only two points are needed
a. Inherited from Comparable
Java code
private static class User implements Comparable<User>
b. Implement the compareTo method
The above public int compareTo(User another) is the subject of comparison
You can see that int compareName = this.name.compareTo(another.getName()); means the comparison name
If it is greater than or returned 1, it is equal to return 0, and if it is less than, it will return -1 .
If equal, compare according to the size of int age.
The above is greater than or equal to return 1, and the above is less than returns -1, which is also the basis for binarySort comparison.
3. Use the overloaded function of Collections sort to sort custom objects
The code is as follows, and the names are still compared first, if they are equal, then the age output is compared
Java code
public class MainTest { public static void main(String[] args) { List<User> userList = new ArrayList<User>(); userList.add(new User("Lucy", 19)); userList.add(new User("Jack", 19)); userList.add(new User("Jim", 19)); userList.add(new User("James", 19)); userList.add(new User("Herry", 19)); userList.add(new User("Luccy", 19)); userList.add(new User("James", 18)); userList.add(new User("Herry", 20)); Collections.sort(userList, new Comparator<User>() { public int compare(User user1, User user2) { int compareName = user1.getName().compareTo(user2.getName()); if (compareName == 0) { return (user1.getAge() == user2.getAge() ? 0 : (user1.getAge() > user2.getAge() ? 1 : -1)); } return compareName; } }); for (User user : userList) { System.out.println(user.getName() + "/t/t" + user.getAge()); } } private static class User { private String name; private int age; public User(String name, int age){ this.name = name; this.age = age; } public String getName() { return name; } public int getAge() { return age; } } }You can see that
Java code
Collections.sort(userList, new Comparator<User>())
It is the subject of comparison and implements the Comparator's comparison method. The following is the principle of this method
Track Collections
Java code
public static <T> void sort(List<T> list, Comparator<? super T> c)
arrive
Java code
public static <T> void sort(T[] a, Comparator<? super T> c)
arrive
Java code
private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off, Comparator c)
You can find the code as follows:
Java code
if (length < INSERTIONSORT_THRESHOLD) { for (int i=low; i<high; i++) for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--) swap(dest, j, j-1); return; }Call Comparator's compare method
4. Comparison of the above two sorting performances
binarySort needs to perform nlg(n) comparisons , and at worst, n^2 movements
mergeSort is constantly performing binary divisions, and after the binary divisions are divided into small parts, it is inserted and sorted. So, nlg(n) times will be compared and nlg(n) times will be moved . But it needs to copy a copy of the source data first, so it will take up twice the space
So you can choose according to your needs
The above article briefly discusses the ordering of object arrays or lists and the sorting principles of Collections is all the content I share with you. I hope you can give you a reference and I hope you can support Wulin.com more.