1 简单排序

1.1 Comparable接口介绍

接口Comparable就是用来定义排序规则的

package com.gtt.pojo;
/**
 * @Author gett
 * @Date 2021/11/18  17:26
 * @Description 学生类
 */
public class Student implements Comparable<Student>{
    private String username;
    private int age;
    public String getUsername() {
        return username;
    }
    public void setUsername(String username) {
        this.username = username;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    public Student(String username, int age) {
        this.username = username;
        this.age = age;
    }
    @Override
    public String toString() {
        return "Student{" +
                "username='" + username + '\'' +
                ", age=" + age +
                '}';
    }
    @Override
    public int compareTo(Student o) {
        return this.getAge()-o.getAge();
    }
}
class Test{
    public static void main(String[] args) {
        Student student1 = new Student("张安", 20);
        Student student2 = new Student("李四", 30);
        Comparable max = getMax(student1, student2);
        System.out.println(max);
    }
    private static Comparable getMax(Student student1, Student student2) {
        int i = student1.compareTo(student2);
        if (i>=0){
            return student1;
        }else{
            return student2;
        }
    }
}

1.2 冒泡排序

排序前：{4,5,6,3,2,1}
排序后：{1,2,3,4,5,6}

原理：

1. 比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置
2. 对每一对相邻元素做相同的工作，从开始第一队到结尾最后一对，最终最后的位置就是最大值

package com.gtt.sort;

import java.util.Arrays;

/**
 * @Author gett
 * @Date 2021/11/18  17:39
 * @Description 冒泡排序
 */

public class Bubble {
    public static void main(String[] args) {
        int [] arr={4,5,6,3,2,1};
        System.out.println("排序前："+ Arrays.toString(arr));
        sort(arr);
        System.out.println("排序后："+Arrays.toString(arr));

    }

    private static void sort(int[] arr) {
        for (int i =arr.length-1; i >0; i--) {
            for (int j=0;j<i;j++){
                if (arr[i]<arr[j]){
                    int temp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
                }
            }

        }
    }
}

时间复杂度：O(N^2)

1.3 选择排序

排序原理：

1. 每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引
2. 交换第一个索引处和最小值所在的索引处的值

package com.gtt.sort;

import java.util.Arrays;

/**
 * @Author gett
 * @Date 2021/11/28  13:16
 * @Description 选择排序
 */

public class Selection {
    public static void main(String[] args) {
        int [] arr={4,6,8,7,9,2,10,1};
        System.out.println("排序前："+ Arrays.toString(arr));
        sort(arr);
        System.out.println("排序后："+Arrays.toString(arr));

    }

    private static void sort(int[] arr) {
        int minIndex;
        for (int i = 0; i < arr.length; i++) {
            minIndex=i;
            for (int j=i
                    +1;j< arr.length;j++){
                if (arr[j]<arr[minIndex]){
                    minIndex=j;
                }
            }
            reaserve(arr,i,minIndex);
        }
    }

    private static void reaserve(int[] arr, int i, int j) {
        int temp;
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;

    }


}

时间复杂度为O(N^2)

1.4 插入排序

原理：

1. 把所有的元素分为两组，已经排序的和未排序的；
2. 找到未排序的组中的第一个元素，向已经排序的组中进行插入；
3. 倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位；

从第二个位置开始比较
把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程

package com.gtt.sort;

import java.util.Arrays;

/**
 * @Author gett
 * @Date 2021/11/28  16:22
 * @Description 插入排序
 */

public class Insertion {
    public static void main(String[] args) {
        int [] arr={4,3,2,10,12,1,5,6};
        System.out.println("排序前："+ Arrays.toString(arr));
        sort(arr);
        System.out.println("排序后："+Arrays.toString(arr));
    }

    private static void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j=i;j>0;j--){
                if (arr[j-1]>arr[j]){
                    int temp;
                    temp=arr[j-1];
                    arr[j-1]=arr[j];
                    arr[j]=temp;
                }else {
                    break;
                }
            }

        }
    }

}

时间复杂度为O(N^2)

2 高级排序