java sort 个人笔记

布满荆棘的人生 2021-12-19 02:19 181阅读 0赞

##  原理 ##

快速排序主要是对那些基本类型数据（int,short,long等）排序， 而归并排序用于对Object类型进行排序。
    使用不同类型的排序算法主要是由于快速排序是不稳定的，而归并排序是稳定的。这里的稳定是指比较相等的数据在排序之后仍然按照排序之前的前后顺序排列。对于基本数据类型，稳定性没有意义，而对于Object类型，稳定性是比较重要的，因为对象相等的判断可能只是判断关键属性，最好保持相等对象的非关键属性的顺序与排序前一致；另外一个原因是由于归并排序相对而言比较次数比快速排序少，移动（对象引用的移动）次数比快速排序多，而对于对象来说，比较一般比移动耗时。
    此外，对大数组排序。快速排序的sort()采用递归实现，数组规模太大时会发生堆栈溢出，而归并排序sort()采用非递归实现，不存在此问题。
    
    总结：
    首先先判断需要排序的数据量是否大于60。
    小于60：使用插入排序，插入排序是稳定的
    大于60的数据量会根据数据类型选择排序方式：
         基本类型：使用快速排序。因为基本类型。1、2都是指向同一个常量池不需要考虑稳定性。
         Object类型：使用归并排序。因为归并排序具有稳定性。
    注意：不管是快速排序还是归并排序。在二分的时候小于60的数据量依旧会使用插入排序

## 实现 ##

int[] array = {10, 3, 6, 1, 4, 5, 9};
    //正序排序
    Arrays.sort(array);//会检查数组个数大于286且连续性好就使用归并排序，若小于47使用插入排序，其余情况使用双轴快速排序
    System.out.println("升序排序：");
    for (int num : array) {
            System.out.println(num);
    }

public class StudentAsc implements Comparable<StudentAsc> {
        private String name;
     
        private Integer age;
     
        public StudentAsc(String name, Integer age) {
            this.name = name;
            this.age = age;
        }
     
        public String getName() {
            return name;
        }
     
        public void setName(String name) {
            this.name = name;
        }
     
        public Integer getAge() {
            return age;
        }
     
        public void setAge(Integer age) {
            this.age = age;
        }
     
        public int compareTo(StudentAsc o) {
            if(null == this.age) {
                return -1;
            }
            if(null == o.getAge()) {
                return 1;
            }
            return this.age.compareTo(o.getAge());
        }
     
        @Override
        public String toString() {
            return "StudentAsc{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }
     
    }
    
    
    
    
    //正序排序，年龄为null时为小
    StudentAsc studentWang = new StudentAsc("王小二", 10);
    StudentAsc studentZhang = new StudentAsc("张三", 1);
    StudentAsc studentGou = new StudentAsc("狗子", 99);
    StudentAsc studentZhao = new StudentAsc("赵六", 40);
    StudentAsc studentLi = new StudentAsc("李四", null);
    List<StudentAsc> studentAscs = new ArrayList<StudentAsc>(Arrays.asList(studentWang, studentZhang, studentGou, studentZhao, studentLi));
    Collections.sort(studentAscs);
    System.out.println("自定义对象，升序排序：");
    for(StudentAsc studentAsc : studentAscs) {
        System.out.println(studentAsc.toString());
    }

## **1、数组内部类排序** ##

Arrays.sort(intervals, new Comparator<Interval>() {
        @Override
        public int compare(Interval o1, Interval o2) {
            if(o1.end != o2.end)
                return o1.end - o2.end;
            return o1.start - o2.start;
        }
    });

## **2、list集合内部类排序** ##

Collections.sort(persons,new Comparator<Person>() {
                @Override
                public int compare(Person p1,Person p2) {
                    if(p1.age > p2.age) return 1;
                    else if (p1.age == p2.age) return 0;
                    else return -1;
                }
            });
        }