Introduction to Comparable
Comparable is a sort interface.
If a class implements the Comparable interface, it means that "this class supports sorting". In addition, the object of the class implementing the Comparable interface can be used as a key in an ordered map (such as TreeMap) or an element in an ordered set (TreeSet), without specifying a comparator. In the interface, x.compareTo(y) is used to compare the sizes of X and y. If it returns a negative number, it means that x is smaller than y; Returns zero, which means x equals y; Returns a positive number, meaning x is greater than y.
Introduction to Comparator
Comparator is the comparator interface. If we need to control the order of a class, and the class itself does not support sorting (that is, it does not implement the Comparable interface); Then, we can create a "comparator of this class" to sort. This "comparator" only needs to implement the comparator interface. In other words, we can "create a new comparator by implementing the comparator class", and then sort the classes through the comparator.
int compare(T o1, T o2) is similar to x.compareTo(y) above. After defining the sorting rule, it returns a positive number. Zero and negative numbers represent greater than, equal to and less than respectively.
The connection between the two
Comparable is equivalent to "internal Comparator", while Comparator is equivalent to "external Comparator".
code implementation
package com.github.compare;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
/**
* @ _ooOoo_
* o8888888o
* 88" . "88
* (| -_- |)
* O\ = /O
* ____/`---'\____
* .' \\| |// `.
* / \\||| : |||// \
* / _||||| -:- |||||- \
* | | \\\ - /// | |
* | \_| ''\---/'' | |
* \ .-\__ `-` ___/-. /
* ___`. .' /--.--\ `. . __
* ."" '< `.___\_<|>_/___.' >'"".
* | | : `- \`.;`\ _ /`;.`/ - ` : | |
* \ \ `-. \_ __\ /__ _/ .-` / /
* ======`-.____`-.___\_____/___.-`____.-'======
* `=---='
* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
* Buddha bless never BUG
*@DESCRIPTION Comparable Is the sorting interface; If a class implements the Comparable interface, it means that "this class supports sorting".
* Comparable Equivalent to "internal comparator"
*@AUTHOR SongHongWei
*@PACKAGE_NAME com.github.compare
**/
public class ComparableAndCompartor
{
public static void main(String[] args)
{
List<House> houses = new ArrayList();
House h1 = new House(95.0, 12000);
House h2 = new House(110.0, 12160);
House h3 = new House(80.0, 16300);
House h4 = new House(150.3, 10690);
houses.add(h1);
houses.add(h2);
houses.add(h3);
houses.add(h4);
comparable(houses);
comparator(houses);
}
/**
*@DESCRIPTION House Class implements the Comparable interface of class and rewrites the compareTo method, so collections The compareTo method we overridden will be called when the sort method
*@AUTHOR SongHongWei
*@TIME 2018/12/14-16:46
*@CLASS_NAME ComparableAndCompartor
**/
private static void comparable(List houses)
{
System.out.printf("Order before unsorted,%s\n", houses);
Collections.sort(houses);
System.out.printf("Order sorted by area size,%s\n", houses);
}
private static void comparator(List houses)
{
System.out.printf("Order before unsorted,%s\n", houses);
Collections.sort(houses, new ComparatorDetail());
System.out.printf("Order sorted by unit price,%s\n", houses);
}
/**
*@DESCRIPTION Implement the comparator interface, rewrite the compare method, and sort in reverse order according to the unit price
*@AUTHOR SongHongWei
*@TIME 2018/12/14-16:49
*@CLASS_NAME ComparableAndCompartor
**/
static class ComparatorDetail implements Comparator<House>
{
@Override
public int compare(House o1, House o2)
{
if (o1.price < o2.price)
return 1;
else if (o1.price > o2.price)
return -1;
return 0;
}
}
}
package com.github.compare;
/**
* @ _ooOoo_
* o8888888o
* 88" . "88
* (| -_- |)
* O\ = /O
* ____/`---'\____
* .' \\| |// `.
* / \\||| : |||// \
* / _||||| -:- |||||- \
* | | \\\ - /// | |
* | \_| ''\---/'' | |
* \ .-\__ `-` ___/-. /
* ___`. .' /--.--\ `. . __
* ."" '< `.___\_<|>_/___.' >'"".
* | | : `- \`.;`\ _ /`;.`/ - ` : | |
* \ \ `-. \_ __\ /__ _/ .-` / /
* ======`-.____`-.___\_____/___.-`____.-'======
* `=---='
* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
* Buddha bless never BUG
*@DESCRIPTION A house object has two attributes: area and unit price
*@AUTHOR SongHongWei
*@PACKAGE_NAME com.github.compare
**/
public class House implements Comparable<House>
{
/*Area of the house*/
protected double proportion;
/*Price per square meter of the house*/
protected double price;
public House(double proportion, double price)
{
this.proportion = proportion;
this.price = price;
}
/**
*@DESCRIPTION Rewrite the compareTo method to use the area of the house for size comparison
*@AUTHOR SongHongWei
*@TIME 2018/12/14-16:18
*@CLASS_NAME House
**/
@Override
public int compareTo(House o)
{
/*The current object has a large area and returns a positive number*/
if (this.proportion > o.proportion)
return 1;
/*The current area is small, and a negative number is returned*/
else if (this.proportion < o.proportion)
return -1;
/*Equal return 0*/
return 0;
}
@Override
public String toString()
{
return "Area" + proportion + "\t The price is" + price;
}
}note appended
Differences between Collections and Collections
Collection is the superior interface of a collection class. The interfaces related to it mainly include List and Set
Collections is a help class for collection classes. It provides a series of static methods to search, sort, thread safety and other operations on various collections
public static void main(String args[]) {
//Note that List implements the Collection interface
List list = new ArrayList();
double array[] = { 112, 111, 23, 456, 231 };
for (int i = 0; i < array.length; i++) {
list.add(new Double(array[i]));
}
Collections.sort(list); //Sort the list from small to large
for (int i = 0; i < array.length; i++) {
System.out.println(list.get(i));
}
// Results: 23.0 111.0 112.0 231.0 456.0
} How Collections call the overridden compareTo method
In the collection framework, the Collections tool class supports two sorting methods:
Collections.sort(List<T> list); Collections.sort(List<T> list, Comparator<? super T> c)
If the list to be sorted contains numbers or characters, you can directly use collections sort(list); When the set or array to be sorted is not a simple numeric type, you need to define your own sorting rules and implement a Comparator comparator.
Collections calls collections Sort (List) method. The method passes a List collection. Here, it is required that the elements contained in the List generic must implement the comparable interface. In addition, all elements in the List must be comparable to each other (that is, e1.compareTo(e2) must not throw ClassCastException for any e1 and e2 elements in the List).
It's written like this in the Java source code
All elements in the list must implement the {@link Comparable}interface.Furthermore, all elements in the list must be <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a {@code ClassCastException} for any elementsCollections.sort source code
public static <T extends Comparable<? super T>> void sort(List<T> list) {
Object[] a = list.toArray();
Arrays.sort(a);
ListIterator<T> i = list.listIterator();
for (int j=0; j<a.length; j++) {
i.next();
i.set((T)a[j]);
}
}As can be seen from the source code, arrays. Is called inside sort Sort method, continue to look down
Arrays.sort source code
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a);
}In the source code, first judge whether to use the traditional sorting method, legacymergesort The userrequested property is false by default, that is, comparabletimsort is selected by default The sort (a) method (traditional merge sort) is the default sort method before 1.5, and the ComparableTimSort.sort() method is executed by default after 1.5. Unless the traditional merge sort is mandatory in the program, the statement is as follows: system setProperty("java.util.Arrays.useLegacyMergeSort", "true"))
Keep watching comparabletimsort Sort (a) source code
ComparableTimSort.sort(a) source code
static void sort(Object[] a) {
sort(a, 0, a.length);
}
static void sort(Object[] a, int lo, int hi) {
rangeCheck(a.length, lo, hi);
int nRemaining = hi - lo;
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi);
binarySort(a, lo, hi, lo + initRunLen);
return;
}
/**
* March over the array once, left to right, finding natural runs,
* extending short natural runs to minRun elements, and merging runs
* to maintain stack invariant.
*/
ComparableTimSort ts = new ComparableTimSort(a);
int minRun = minRunLength(nRemaining);
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi);
// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen);
runLen = force;
}
// Push run onto pending-run stack, and maybe merge
ts.pushRun(lo, runLen);
ts.mergeCollapse();
// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);
// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;
}nRemaining indicates the number of objects that are not sorted. Before the method is executed, if the number is less than 2, sorting is not required.
If 2 < = nremaining < = 32, it is min_ The initial value of merge indicates that the array to be sorted is a small array. You can use the mini timsort method for sorting, otherwise you need to use merge sorting.
Mini timsort sorting method: first find the first ascending sequence in the array starting from subscript 0, or find the descending sequence, convert it to ascending sequence, and put it into the array again. Take this ascending array as the initial array, and insert each subsequent element into the initial array through dichotomy sorting. Note that here we call the rewritten compareTo() method.
private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
assert lo < hi;
int runHi = lo + 1;
if (runHi == hi)
return 1;
// Find end of run, and reverse range if descending
if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending
while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
runHi++;
reverseRange(a, lo, runHi);
} else { // Ascending
while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)
runHi++;
}
return runHi - lo;
}Source: blog csdn. net/u010859650**/article/details/85009595
Recent hot article recommendations:
1.1000 + Java interview questions and answers (2021 latest version)
2.Hot! The Java collaboration is coming...
3.Play big! Log4j 2.x re explosion...
4.Spring Boot 2.6 was officially released, a wave of new features..
5.Java development manual (Songshan version) is the latest release. Download it quickly!
Feel good, don't forget to like + forward!