1 简单排序

1.1 Comparable接口介绍

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

  1. package com.gtt.pojo;
  2. /**
  3. * @Author gett
  4. * @Date 2021/11/18 17:26
  5. * @Description 学生类
  6. */
  7. public class Student implements Comparable<Student>{
  8. private String username;
  9. private int age;
  10. public String getUsername() {
  11. return username;
  12. }
  13. public void setUsername(String username) {
  14. this.username = username;
  15. }
  16. public int getAge() {
  17. return age;
  18. }
  19. public void setAge(int age) {
  20. this.age = age;
  21. }
  22. public Student(String username, int age) {
  23. this.username = username;
  24. this.age = age;
  25. }
  26. @Override
  27. public String toString() {
  28. return "Student{" +
  29. "username='" + username + '\'' +
  30. ", age=" + age +
  31. '}';
  32. }
  33. @Override
  34. public int compareTo(Student o) {
  35. return this.getAge()-o.getAge();
  36. }
  37. }
  38. class Test{
  39. public static void main(String[] args) {
  40. Student student1 = new Student("张安", 20);
  41. Student student2 = new Student("李四", 30);
  42. Comparable max = getMax(student1, student2);
  43. System.out.println(max);
  44. }
  45. private static Comparable getMax(Student student1, Student student2) {
  46. int i = student1.compareTo(student2);
  47. if (i>=0){
  48. return student1;
  49. }else{
  50. return student2;
  51. }
  52. }
  53. }

1.2 冒泡排序

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

原理:

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

image.png

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. 交换第一个索引处和最小值所在的索引处的值

image.png

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次可完成排序过程

image.png

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 高级排序