此文介绍了冒泡排序、选择排序、插入排序

排序可视化网站 https://visualgo.net/zh/sorting 可以更快速理解！

本文会随着作者日常学习进行补充及内容修正

1.冒泡排序

通过多次遍历，判断相邻两个之间大小,每次都能取到最大值

第一次遍历0~N-1 最大值为N-1位

第二次遍历0~N-2 第二大值为N-2位

。。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void bubbleSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    for(int e = arr.length - 1;e > 0;e--){   //最后一次是e=1，下面的遍历为0~1
        for(int i = 0;i < e;i++){    //0~e
            if(arr[i] > arr[i+1]){
               swap(arr,i,i++); 
            }
        }
    }
}
//交互位置 如果i和j是同一个位置，会出错
public static void swap(int[] arr ,int i,int j){
    arr[i]=arr[i]^arr[j];
    arr[j]=arr[i]^arr[j];
    arr[i]=arr[i]^arr[j];
}

2.选择排序

遍历查找最小值，然后交互位置

第一次遍历0~N-1 最小值为第0位

第二次遍历1~N-1 第二小值为第1位

。。。。

总结为i~N-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void selectSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    for(int i = 0;i < arr.length - 1;i++){
        int minIndex = i;
        for(int j = i + 1;j < arr.length;j++){
            minIndex = arr[j] < arr[mindex] ? j :minIndex;
        }
        swap(arr, i ,minIndex)
    }
}
//交互位置
public static void swap(int[] arr ,int i,int j){
    int temp =arr[i];
    arr[i] =arr[j];
    arr[j]=temp;
}

3.插入排序

0~1上有序

0~2上有序

。。。。

0~i上有序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void insertSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    for(int i = 1; i < arr.length; i++){
        for(int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--){   
          swap(arr, j ,j + 1);  
        }
    }
}
//交互位置 如果i和j是同一个位置，会出错
public static void swap(int[] arr ,int i,int j){
    arr[i]=arr[i]^arr[j];
    arr[j]=arr[i]^arr[j];
    arr[i]=arr[i]^arr[j];
}