10-比较器

重新认识 Arrays 类
两种比较器的使用
数据结构——二叉树（Binary Tree）

Arrays 类

java.util.Arrays.sort()可以实现数组的排序。

这个类里存在二分查找法

public static int binarySearch(long[] a, long key) {}

还提供了数组比较，但是要想判断数组是否相同，需要顺序完全一致：

import java.util.Arrays;

class Main {
    public static void main(String [] args){
        int dataA[] = new int[] {1,2,3};
        int dataB[] = new int[] {2,1,3};
        System.out.println(Arrays.equals(dataA, dataB));
        Arrays.sort(dataB);
        System.out.println(Arrays.equals(dataA, dataB));
    }
}

out:
false
true

填充数组：

public static void fill(T[] a, T val) {}

将数组变为字符串输出：

public static String toString(T[] a) {}

范例：

import java.util.Arrays;

class Main {
    public static void main(String [] args){
        int data[] = new int[10];
        Arrays.fill(data, 3);
        System.out.println(Arrays.toString(data));
    }
}

out:
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3]

基操，比较少出现。

比较器：Comparable（核心）

Arrays 类里面可以直接利用 sort（）方法实现对象数组的排序。

import java.util.Arrays;

class Book{
    private String name;
    private double price;

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

    @Override
    public String toString() {
        return "书名：" + this.name + "，价格：" + this.price;
    }
}

class Main {
    public static void main(String [] args){
        Book [] books = new Book[]{
                new Book("1", 1),
                new Book("2", 2),
                new Book("3", 3),
                new Book("4", 4)
            };
        Arrays.sort(books);
        System.out.println(Arrays.toString(books));
    }
}


out:
Exception in thread "main" java.lang.ClassCastException: Book cannot be cast to java.lang.Comparable
	at java.util.ComparableTimSort.countRunAndMakeAscending(ComparableTimSort.java:320)
	at java.util.ComparableTimSort.sort(ComparableTimSort.java:188)
	at java.util.Arrays.sort(Arrays.java:1246)
	at Main.main(Main.java:26)

此类异常的原因只有一个：两个没有关系的对象发生了强制性的转换。

每一个对象实际上值保留有地址信息，地址里面有内容。如果普通 int 型数组比较大小就够了。如果是对象数组，里面包含的如果只是编码（地址），比较是没有意义的。

因此要实现 Comparable 接口：

public interface Comparable<T> {
    public int compareTo(T o);
}

String 类就是 Comparable 的子类。

建议覆写 compareTo（）返回三种数据：

大于：1
等于：0
小于：-1

实现比较

import java.util.Arrays;

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

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

    @Override
    public String toString() {
        return "书名：" + this.name + "，价格：" + this.price;
    }

    @Override
    public int compareTo(Book o) {
        // Arrays.sort()会自动调用此方法进行比较
        if (this.price > o.price) {
            return 1;
        } else if (this.price < o.price) {
            return -1;
        } else return 0;
    }
}

class Main {
    public static void main(String[] args) {
        Book[] books = new Book[]{
                new Book("1", 1),
                new Book("2", 2),
                new Book("3", 3),
                new Book("4", 4)
        };
        Arrays.sort(books);
        System.out.println(Arrays.toString(books));
    }
}

Arrays.sort()会自动调用 compareTo（）方法进行比较。

数据结构——BinaryTree

树是比链表更复杂的动态数组。

二叉排序树，每个节点的左子树的值总比节点小，右子树的值总比节点大

中序遍历会得到有序序列。

实现二叉树：

step1：实现数据类：

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

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

    @Override
    public String toString() {
        return "书名：" + this.name + "，价格：" + this.price;
    }

    @Override
    public int compareTo(Book o) {
        // Arrays.sort()会自动调用此方法进行比较
        if (this.price > o.price) {
            return 1;
        } else if (this.price < o.price) {
            return -1;
        } else return 0;
    }
}

定义二叉树，所有数据结构都要有 Node 类的支持

class BinaryTree{
    private class Node{
        private Comparable data;
        private Node left;
        private Node right;
        public Node(Comparable data){
            this.data = data;
        }
        public void addNode(Node newNode){
            if (this.data.compareTo(newNode.data) > 0){ // 升降序调节
                if (this.left == null){
                    this.left = newNode;
                }else {
                    this.left.addNode(newNode);
                }
            }else {
                if (this.right == null){
                    this.right = newNode;
                }else {
                    this.right.addNode(newNode);
                }
            }
        }

        public void toArrayNode() {
            if (this.left!=null){
                this.left.toArrayNode();
            }
            BinaryTree.this.retData[BinaryTree.this.foot++] = this.data;
            if (this.right!=null){
                this.right.toArrayNode();
            }
        }
    }
    private Node root; //定义根节点
    private int count;
    private Object[] retData;
    private int foot;
    public void add (Object obj){
        Comparable com = (Comparable) obj;
        Node newNode = new Node(com);
        if (this.root == null){
            this.root = newNode;
        }else{
            this.root.addNode(newNode);
        }
        this.count++;
    }

    public Object[] toArray(){
        if (this.root == null){
            return null;
        }
        this.foot=0;
        this.retData = new Object[this.count];
        this.root.toArrayNode();
        return this.retData;
    }
}

二叉树中所有操作符合中序遍历！

最后实现主函数：

class Main {
    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        bt.add(new Book("test1", 10));
        bt.add(new Book("test2", 30));
        bt.add(new Book("test3", 50));
        bt.add(new Book("test4", 5));
        System.out.println(Arrays.toString(bt.toArray()));
    }
}

out:
[书名：test4，价格：5.0, 书名：test1，价格：10.0, 书名：test2，价格：30.0, 书名：test3，价格：50.0]

挽救的比较器：Comparator

Comparable 接口需要在类定义的时候就实现了，如果要在后期实现比较就要使用 Comparator（不修改原有的类）

java.util.Comparator

@FunctionalInterface
public interface Comparator<T> {
    int compare(T o1, T o2);
    boolean equals(Object obj);
}

因此只需要覆写 compare 方法。（equals 方法是 Object 类所拥有的）

需要重新编写一个工具类来实现比较！

实现比较工具

class BookComparator implements Comparator<Book>{
    @Override
    public int compare(Book o1, Book o2) {
        if (o1.getPrice() > o2.getPrice()){
            return 1;
        }else if (o1.getPrice() < o2.getPrice()){
            return -1;
        }else return 0;
    }
}

之前使用 Comparable 接口的时候直接使用的 Arrays.sort（）方法进行排序的，现在更换了 Comparator 之后，可以使用另一个重载的 sort 方法。

public static <T> void sort(T[] a, Comparator<? super T> c) {}

重新实现排序

class Main {
    public static void main(String[] args) {
        Book books[] = new Book[]{
                new Book("test1", 10),
                new Book("test2", 30),
                new Book("test3", 50),
                new Book("test4", 5)
        };
        Arrays.sort(books,new BookComparator());
        System.out.println(Arrays.toString(books));
    }
}

out：
[书名：test4，价格：5.0, 书名：test1，价格：10.0, 书名：test2，价格：30.0, 书名：test3，价格：50.0]

使用 Comparator 比较麻烦。尽量使用 Comparable。

面试题：解释 Comparable 和 Comparator 的区别

如果对象数组要进行排序，那么必须设置排序规则，可以使用上述两个接口。
java.lang.Comparable 是在一个类定义的时候要实现 compareTo（）。
java.util.Comparator 是在一个类定义之后，专门实现 compare（）方法的工具类。

Rainning in the utopia

10-比较器

Arrays 类

比较器：Comparable（核心）

数据结构——BinaryTree

挽救的比较器：Comparator