1.自然排序

在Java中提供了一个Comparable接口，在接口中定义了public int compareTo(To);抽象方法
该方法返回一个整数值，通过obj1.compareTo(obj2)，对两个对象进行比较，如果返回值是0则表明两数相等，如果返回正整数则表明obj1大于obj2，否则如果返回负整数则表明obj1小于obj2

TreeSet会自动调用compareTo(Object obj)方法进行元素之间的排序，然后以升序排列

在Set集合中的TreeSet章中说过，Set其实就是Map集合的特殊表现形式(value为null的集合)那么跟踪源码，下面这个add方法的注释，说明排序是通过自然排序的

    /**
     * Adds the specified element to this set if it is not already present.
     * More formally, adds the specified element {@code e} to this set if
     * the set contains no element {@code e2} such that
     * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
     * If this set already contains the element, the call leaves the set
     * unchanged and returns {@code false}.
     *
     * @param e element to be added to this set
     * @return {@code true} if this set did not already contain the specified
     *         element
     * @throws ClassCastException if the specified object cannot be compared
     *         with the elements currently in this set
     * @throws NullPointerException if the specified element is null
     *         and this set uses natural ordering, or its comparator
     *         does not permit null elements
     */
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

再次跟进到put方法

private final Comparator<? super K> comparator;
//put方法作为添加元素和修改元素的两种功能，添加元素的时候统一返回的是null，修改元素的时候统一返回的是修改之前的元素的value。作为TreeSet方法很明显只有返回null
    public V put(K key, V value) {
        Entry<K,V> t = root;//根节点
        if (t == null) {//判断根节点是否为空
            compare(key, key); // type (and possibly null) check(检查类型可能为空)
            
            root = new Entry<>(key, value, null);//将parent赋值为null并作为根节点
            size = 1;
            modCount++;
            return null;//返回null，跳过余下代码
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;//判断comparator是定制排序还是自然排序
        //如果comparator是自然排序
        if (cpr != null) {//判断 comparator 是否为null，如果是自然顺序则为null
        	//通过循环比较key的值计算将要添加的结点的位置
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);//如果发现有某个结点的key值和将要添加的key的值相等，说明这是修改操作，修改其value值返回旧value值
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);//如果根节点不是空
        }
        else {//如果在创建对象的时候并没有从外部传入comparator比较器
            if (key == null)//判断key的值是否为null
                throw new NullPointerException();//如果是就抛出空指针异常
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);//调用方法重构红黑树
        size++;
        modCount++;
        return null;
    }

通过上述源码解析我们很容易就发现，我们传入值到add方法中，会调用put方法，put方法将自然排序和定制排序进行了隔离，而源码中将接口Comparator设置为finale类型
并在put方法中进行判断，
如果是Comparator定制排序(默认排序)，则可以通过key的compare排序后判断key值是否相等，如果不相等则生成数的左或右节点，相等则替换(在TreeSet中value值都为null，所以即使替换也看不出效果)，
如果是Comparable自然排序(外传入排序(因为包装类或String类型中都写有自然排序方法，如下代码))，那么private final Comparator<? super K> comparator;就会是null，则cpr就是null，那么程序就会执行自然排序，排序并在不相等的情况下生成树的左或右子节点，相等则替换
最后重构红黑树

    public int compareTo(String anotherString) {
        int len1 = value.length;
        int len2 = anotherString.value.length;
        int lim = Math.min(len1, len2);
        char v1[] = value;
        char v2[] = anotherString.value;

        int k = 0;
        while (k < lim) {
            char c1 = v1[k];
            char c2 = v2[k];
            if (c1 != c2) {
                return c1 - c2;
            }
            k++;
        }
        return len1 - len2;
    }

看完String类中重写的Comparable接口中的compareTo方法后就会更加容易理解，为什么注释中会说是通过自然排序了
因为这是为了使对象通过一个默认的顺序进行排序，如果是已经定义好的(如：String、Integer等)
所有添加的数据都按照这个顺序进行排序，则称为自然排序

但是我们发现一个问题，即我们传入的值之间必须是需要进行比较的
那么问题来了，如果传入相同的对象确实，可以很容易的通过某种规则进行比较，但是不同的对象呢？

代码如下

package TreeSetTest;

import java.util.Date;
import java.util.TreeSet;

public class Test1 {
	public static void main(String[] args) {
		TreeSet ts=new TreeSet();
		ts.add(new String());
		ts.add(new Date());
	}
}

会出现java.lang.String cannot be cast to java.util.Date的错误，无法从String转换成Date，在String类中的compareTo方法中对应的形参是该类对象，如果传入一个Date类的对象，对象之间会发生强制转换，而我们知道，这样是并不能发生转换的

package TreeSetTest;

import java.util.Date;
import java.util.TreeSet;
//这样又是可以的了
public class Test1 {
	public static void main(String[] args) {
		TreeSet ts=new TreeSet();
		ts.add(new String());
		ts.add(new String());

	}
}

所以在TreeSet中是必须要求对象是相同的并且自然排序需要写在对象所在的类中(因为是外传入排序)

2.定制排序

定制排序是使用的java中提供的Comparator接口，自然排序就是说排序发生在封装类中，用户无法使用，但是定制排序是可以通过用户自己实现的，在创建TreeSet对象时就可以自定义Comparator接口中的int compare(T o1,To2)方法，比较两个参数的大小，如果该方法返回正整数则表明o1大于o2，如果返回0则说明o1=o2，如果返回负整数则说明o1小于o2

整数类型

package TreeSetTest;

import java.util.Comparator;
import java.util.Date;
import java.util.TreeSet;

public class Test1{
	public static void main(String[] args) {
		TreeSet<Person> ts=new TreeSet<Person>(new Comparator(){
			@Override
			public int compare(Object o1,Object o2) {
				Person p1=(Person)o1;
				Person p2=(Person)o2;
				return -(p1.getAge()-p2.getAge());
			}
		});
		ts.add(new Person(15,"小明","男"));
		ts.add(new Person(17,"小明","女"));
		System.out.println(ts);
	}
}

输出如下

[Person [age=17, name=小明, sex=女], Person [age=15, name=小明, sex=男]]

String类型

package TreeSetTest;

import java.util.Comparator;
import java.util.Date;
import java.util.TreeSet;

public class Test1{
	public static void main(String[] args) {
		TreeSet<Person> ts=new TreeSet<Person>(new Comparator(){
			@Override
			public int compare(Object o1,Object o2) {
				Person p1=(Person)o1;
				Person p2=(Person)o2;
				return p1.getName().compareTo(p2.getName());
			}
		});
		ts.add(new Person(15,"小明","男"));
		ts.add(new Person(17,"小红","女"));
		System.out.println(ts);
	}
}

输出结果：

[Person [age=15, name=小明, sex=男], Person [age=17, name=小红, sex=女]]

当字符串相同情况

说明：这里在比较值相等的情况，是添加无效的，有人会说map中为什么可以覆盖，那是因为key值并没有变，而是修改了Value值，而在TreeSet中的值都是key值，value为null值，所以TreeSet中出现相同值是不会报错也不会被替换的

如下测试：

package TreeSetTest;

import java.util.Comparator;
import java.util.Date;
import java.util.TreeSet;

public class Test1{
	public static void main(String[] args) {
		TreeSet<Person> ts=new TreeSet<Person>(new Comparator<Person>(){
			@Override
			public int compare(Person o1, Person o2) {
				Person p1=(Person)o1;
				Person p2=(Person)o2;
				return p1.getName().compareTo(p2.getName());
			}
		});
		ts.add(new Person(15,"小明","男"));
		ts.add(new Person(17,"小明","女"));
		System.out.println(ts);
	}
}

输出结果：

[Person [age=15, name=小明, sex=男]]

这里我们需要注意的是，数值是可以直接减的，但是字符串等类类型通过调用自然排序的方法是最简单有效的，至于是升序还是降序，前面加负号即可

写在前面： 我是「扬帆向海」，这个昵称来源于我的名字以及女朋友的名字。我热爱技术、热爱开源、热爱编程。技术是开源的、知识是共享的。

这博客是对自己学习的一点点总结及记录，如果您对 Java、算法 感兴趣，可以关注我的动态，我们一起学习。

用知识改变命运，让我们的家人过上更好的生活。

比如Integer，double等基本类型数据，Java可以对他们进行比较排序，但是在 Java 中经常会涉及到对象数组的排序问题，那么就涉及到对象之间的比较问题 。

一、java中的sort()方法

在java.util.Collections类中有个sort()方法，主要是用来给数组排序

public class CompareTest1 {
    @Test
    public void test() {
        String[] arr = new String[]{"AA", "SS", "FF", "OO", "EE", "HH"};
        System.out.println("排序之前： " + Arrays.toString(arr));
        Arrays.sort(arr);
        System.out.println("排序之后： " + Arrays.toString(arr));
    }
}

代码执行结果：

排序之前： [AA, SS, FF, OO, EE, HH]
排序之后： [AA, EE, FF, HH, OO, SS]

需求：商场有一批水果，对水果的价格进行排序

水果类：

public class Fruit {
    private String name;
    private double price;

    public Fruit() {
    }

    public Fruit(String name, double price) {
        this.name = name;
        this.price = price;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getPrice() {
        return price;
    }

    public void setPrice(double price) {
        this.price = price;
    }

    @Override
    public String toString() {
        return "Fruit{" +
                "name='" + name + '\'' +
                ", price=" + price +
                '}';
    }
}

测试类：

public class CompareTest2 {
    @Test
    public void test() {
        Fruit[] arr = new Fruit[5];
        arr[0] = new Fruit("apple", 18);
        arr[1] = new Fruit("pear", 6);
        arr[2] = new Fruit("banana", 14);
        arr[3] = new Fruit("watermelon", 26);
        arr[4] = new Fruit("tomato", 6);
        System.out.println("排序之前： " + Arrays.toString(arr));
        // 排序
        Arrays.sort(arr);
        System.out.println("排序之后： " + Arrays.toString(arr));
    }
}

程序将会报错：

java.lang.ClassCastException: xxx.Fruit cannot be cast to java.lang.Comparable

报错原因：类型转换错误。

为了解决这个错误，对象之间的排序将用到比较器。

Java 实现对象排序的方式有两种：

自然排序： java.lang.Comparable

定制排序： java.util.Comparator

二、自然排序：Comparable

1.自然排序的定义

Comparable 接口强行对实现它的每个类的对象进行整体排序

2.实现过程

实现 Comparable接口的类必须实现 compareTo(Object obj) 方法，两个对象通过 compareTo方法的返回值来比较大小 。
① 如果当前对象 this 大于形参对象 obj 则返回正整数；
② 如果当前对象 this 小于 形参对象 obj则返回 负整数；
③ 如果当前对象 this 等于 形参对象 obj 则返回零 。
实现 Comparable接口的对象列表（和数组）可以通过 Collections.sort 或 Arrays.sort 进行自动排序。
实现此接口的对象可以用作有序映射中的键或有序集合中的集合，无需指定比较器

为了解决类型转换错误，在水果类里面实现Comparable接口。

3.示例代码

水果类：

public class Fruit implements Comparable<Fruit> {
    private String name;
    private double price;

    public Fruit() {
    }

    public Fruit(String name, double price) {
        this.name = name;
        this.price = price;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getPrice() {
        return price;
    }

    public void setPrice(double price) {
        this.price = price;
    }

    @Override
    public String toString() {
        return "Fruit{" +
                "name='" + name + '\'' +
                ", price=" + price +
                '}';
    }

    // 水果价格从低到高进行排序，若价格相同则按水果名称从高到低排序
    @Override
    public int compareTo(Fruit fruit) {
        if (this.price > fruit.price) {
            return 1;
        } else if (this.price < fruit.price) {
            return -1;
        } else {
            // this.name.compareTo(fruit.name) 按名称从低到高，前面加负号，表示相反
            return -this.name.compareTo(fruit.name);
        }
    }
}

注：测试类代码同Test2
代码执行结果：

排序之前： [Fruit{name='apple', price=18.0}, Fruit{name='pear', price=6.0}, Fruit{name='banana', price=14.0}, Fruit{name='watermelon', price=26.0}, Fruit{name='tomato', price=6.0}]
排序之后： [Fruit{name='tomato', price=6.0}, Fruit{name='pear', price=6.0}, Fruit{name='banana', price=14.0}, Fruit{name='apple', price=18.0}, Fruit{name='watermelon', price=26.0}]

三、定制排序 ：Comparator

在实际开发中，遇到当元素的类型实现了Comparable 接口，但是它的排序方式不适合当前的操作；或者根本没有实现Comparable
接口，而又不方便修改代码。那么可以考虑使用 Comparator 的对象进行排序。

1.实现过程

定义一个比较器对象；
重写 compare(Object o1,Object o2) 方法，比较 o1 和 o2 的大小：
① 如果方法返回正整数，则表示 o1 大于 o2 ；
② 如果方法返回 0 ，表示相等；
③ 如果方法返回负整数，表示o1 小于 o2 。

可以 将 Comparator 传递给 sort 方法，从而允许在排序顺序上实现精确控制 。

2.示例代码

public class CompareTest3 {
    /**
     * 按字符从大到小进行排序
     */
    @Test
    public void test() {
        String[] arr = new String[]{"AA", "CC", "KK", "MM", "GG", "FF", "DD"};
        System.out.println("原来的字符串： " + Arrays.toString(arr));
        Arrays.sort(arr, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return -o1.compareTo(o2);
            }
        });
        System.out.println("按字符从大到小排序后的字符串： " + Arrays.toString(arr));
    }
}

代码执行结果：

原来的字符串： [AA, CC, KK, MM, GG, FF, DD]
按字符从大到小排序后的字符串： [MM, KK, GG, FF, DD, CC, AA]

对水果的价格进行排序

注：水果类同前，节省篇幅，在此不再重复。

public class CompareTest4 {
    @Test
    public void test() {
        Fruit[] arr = new Fruit[5];
        arr[0] = new Fruit("apple", 18);
        arr[1] = new Fruit("pear", 6);
        arr[2] = new Fruit("banana", 14);
        arr[3] = new Fruit("watermelon", 26);
        arr[4] = new Fruit("watermelon", 6);
        System.out.println("排序之前： " + Arrays.toString(arr));

        Arrays.sort(arr, new Comparator<Fruit>() {
            // 按照水果名称从低到高排序,若名称相同则按照价格从高到低排序
            @Override
            public int compare(Fruit o1, Fruit o2) {
                if (o1.getName().equals(o2.getName())) {
                    return -Double.compare(o1.getPrice(), o2.getPrice());
                } else {
                    return o1.getName().compareTo(o2.getName());
                }
            }
        });
        System.out.println("排序之后： " + Arrays.toString(arr));
    }
}

代码执行结果：

排序之前： [Fruit{name='apple', price=18.0}, Fruit{name='pear', price=6.0}, Fruit{name='banana', price=14.0}, Fruit{name='watermelon', price=26.0}, Fruit{name='watermelon', price=6.0}]
排序之后： [Fruit{name='apple', price=18.0}, Fruit{name='banana', price=14.0}, Fruit{name='pear', price=6.0}, Fruit{name='watermelon', price=26.0}, Fruit{name='watermelon', price=6.0}]

当定制排序和自然排序同时存在时，最终的排序结果是按照定制排序进行排序的。

上一篇 聊聊 StringBuffer 与 StringBuilder

一、自然排序

自然排序：类实现了java.lang.Comparable接口，重写compareTo()的规则

如果当前对象this大于形参对象obj，则返回正整数；如果当前对象this小于形参对象obj，则返回负整数；如果当前对象this等于参数对象obj，则返回零。

1.Person类

public class Person implements Comparable<Person> {
    private Integer age;

    public Person(Integer age) {
        this.age = age;
    }

    @Override
    public int compareTo(Person person) {
        return this.age - person.age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "age=" + age +
                '}';
    }
}

2.测试

Arrays有方法public static void sort(Object[] a)

@Test
public void test1() {
    Person[] peoples = new Person[4];
    peoples[0] = new Person(11);
    peoples[1] = new Person(19);
    peoples[2] = new Person(18);
    peoples[3] = new Person(10);

    Arrays.sort(peoples);

    System.out.println(Arrays.toString(peoples));
}

3.结果

二、定制排序

定制排序：java.util.Comparator

当元素的类型没有实现java.lang.Comparable接口而又不方便修改代码时，那么可以考虑使用Comparator的对象来排序

1.Person类

public class Person {
    private Integer age;

    public Person(Integer age) {
        this.age = age;
    }

    public Integer getAge() {
        return age;
    }

    public void setAge(Integer age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "age=" + age +
                '}';
    }
}

2.测试

Arrays有方法public static <T> void sort(T[] a, Comparator<? super T> c)

@Test
public void test2() {
    Person[] peoples = new Person[4];
    peoples[0] = new Person( 13);
    peoples[1] = new Person(19);
    peoples[2] = new Person(17);
    peoples[3] = new Person(16);

    Arrays.sort(peoples, new Comparator<Person>() {
        @Override
        public int compare(Person person1, Person person2) {
            return person1.getAge() - person2.getAge();
        }
    });

    System.out.println(Arrays.toString(peoples));
}

3.结果