数据结构与算法冒泡排序Java外比较器和内比较器(排序专题)

Maynor

发布于 2021-12-07 11:33:43

4100

发布于 2021-12-07 11:33:43

文章被收录于专栏：最新最全的大数据技术体系最新最全的大数据技术体系

大家好,我是ChinaManor,直译过来就是中国码农的意思,我希望自己能成为国家复兴道路的铺路人,大数据领域的耕耘者,平凡但不甘于平庸的人。要是数据结构那么简单没人想当码农,为了摆脱码农还是得硬着头皮学

目的:为了更好地学习和理解数组排序，为了面试作准备冒泡排序：是一种计算机科学领域较常见的排序算法。因为它的算法就如同碳酸饮料中二氧化碳气泡最终会上浮到顶端一样，所以形象化称为“冒泡排序”

原理小结：

依次“对比”或“交换”数组中每两个相邻的元素，使最值元素通过交换，慢慢“浮到”数组顶端。

课堂代码：

/**
 * 冒泡入门-第三版
 *
 * 相邻元素：  j  和  j+1
 * @param args
 */
public static void main(String[] args) {
    int[] arr = {55,44,11};
    System.out.println("冒泡前："+ Arrays.toString(arr));
    for (int i = 1; i < arr.length; i++) {
        for (int j = 0; j <arr.length-i ; j++) {
            if(arr[j]>arr[j+1]){
                //交换
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }
    }

}


/**
 * 冒泡入门-第三版
 *
 * 相邻元素：  j  和  j+1
 * @param args
 */
public static void main(String[] args) {
    int[] arr = {55,44,11};
    System.out.println("冒泡前："+ Arrays.toString(arr));
    for (int i = 1; i < arr.length; i++) {
        for (int j = 0; j <arr.length-i ; j++) {
            if(arr[j]>arr[j+1]){
                //交换
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }
    }

}

升序—从小到大： arr[j]>arr[j+1] 降序—从大到小： arr[j]

如果自己写排序，费时费力所以下面我们介绍两种为List集合进行排序

5.2准备数据 Person类：

public class Person {
    private String name;
    private int age;
    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public Person() {
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
}

Demo1类：

public class Demo1 {
    public static void main(String[] args) {
        //1、准备数据
        ArrayList<Person> plist = new ArrayList<Person>();
        plist.add(new Person("小1",15));
        plist.add(new Person("小2",19));
        plist.add(new Person("小3",11));
        plist.add(new Person("小4",16));
        plist.add(new Person("小5",12));
    }
}

5.3Comparator比较器（外比较器）

凡是实现了Comparator接口的类，都是外比较器类。只要重写接口中的compare方法，即可完成比较。示例：

public static void main(String[] args) {
    //1、准备数据
    List<Person> plist = new ArrayList<Person>();
    plist.add(new Person("小1",15));
    plist.add(new Person("小2",19));
    plist.add(new Person("小3",11));
    plist.add(new Person("小4",16));
    plist.add(new Person("小5",12));
    //2、处理数据：通过人的年龄，比较大小。
plist.sort(new Comparator<Person>() {
    @Override
    public int compare(Person o1, Person o2) {
        return o1.getAge()-o2.getAge();
    }
});

    System.out.println(plist);
}

建议：无需记忆何谓从大到小，何谓从小到大，尝试一次即可

另一种方式：

Collections.sort(plist, new Comparator() {
    @Override
    public int compare(Person o1, Person o2) {
        return o1.getAge()-o2.getAge();
    }
});

注意：正数、0： o1和o2位置就不会交换 负数： o1和o2位置交换

使用环境：适用于一题多解的模式。 Person类，先进行年龄排序，后面可能还会进行成绩排序，学号排序

5.4Comparable接口（内比较器）

需要Person类自己实现Comparable接口，通过Collections工具进行排序比较 Person类：

public class Person implements Comparable{
    private String name;
    private int age;
    @Override
    public int compareTo(Object o) {
        return this.getAge()-((Person)o).getAge();
    }
    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public Person() {
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
}

Demo1类：

public static void main(String[] args) {
    //1、准备数据
    List<Person> plist = new ArrayList<Person>();
    plist.add(new Person("小1",15));
    plist.add(new Person("小2",19));
    plist.add(new Person("小3",11));
    plist.add(new Person("小4",16));
    plist.add(new Person("小5",12));
    //2、处理数据
    Collections.sort(plist);
    System.out.println(plist);
}

注意：比较器的CompareTo方法：正数、0：不会交换负数：交换位置

排序总结

如果一个类在不同题目中以各种方式排序，就用Comparator外比较器。例如：Person类在题目1中用年龄排序在题目2中用分数排序在题目3中用生日排序这时，一道题就要写一个外比较器

如果一个类在不同题目中以同一种方式排序，就用Comparable内比较器例如：Person类在题目1、题目2、题目3中都是用年龄排序，这时，就可以统一在Person类中写一个内比较器

一个类在不同题目中，经常是要不同方式排序， 外比较器使用频率最高

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2021-06-24 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度