1、选择排序

1.1、选择排序思路

选择排序( select sorting)也是一种简单的排序方法。

它的基本思想是:第一次从arr[0]到arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]到arr[n - 1]中选取最小值，与arr[1]交换，第三次从arr[2]到arr[n-1]中选取最小值，与arr[2]交换，…，第 i 次从arr[i-1]到arr[n-1]中选取最小值与arr[i-1]交换，…，第n-1次从arr[n-2]到arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

1.2、思路分析图

image-20210330140137749

1.3、代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        int minValue = arr[i];
        // 这里需要从 i + 1下标开始
        for (int j = i + 1; j < arr.length; j++) {
            if(arr[j] < minValue) {
                minValue = arr[j];
                minIndex = j;
            }
        }
        //退出循环后，交换arr[i]与后面数组中找到的最小值
        //这里注意，如果minIndex = i，那么证明当前arr[i]是后面数组的最小值
        //此时不需要发生交换
        if(minIndex != i) {
            arr[minIndex] = arr[i];
            arr[i] = minValue;
        }
    }
}

1.4、测试

在main方法中创建一个数组，使用选择排序进行排序

1
2
3
int[] arr = {101,88,777,1,-100,108};
selectSort(arr);
System.out.println(Arrays.toString(arr));

排序结果如下

image-20210330142416210

2、插入排序

2.1、插入排序算法介绍

插入排序属于内部排序法，是对要排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的

2.2、基本思想

插入排序的基本思想是：把n个待排序元素看为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中有 n - 1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，然后把它插入到有序表的适当位置，使之成为新的有序表

2.3、思路图

image-20210330142927006

2.4、代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int insertVal = arr[i];
        int insertIndex = i - 1;
        //1 insertIndex >= 0保证数组下标不越界
        //2 insertVal < arr[insertIndex]证明insertVal还没有找到待插入位置
        while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
            //让数组元素往后挪一位
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex + 1] = insertVal;
    }
}

3、快速排序

3.1、介绍

快速排序（Quick sort）是对冒泡排序的一种改进；

基本思想是：通过一趟排序将要排序的数据分割为独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据都变为有序序列。

3.2、示意图

image-20210330144811648

3.3、代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public static void quickSort(int[] arr, int left, int right) {
    int l = left;
    int r = right;
    int temp = 0;
    //确定中轴值
    int pivot = arr[(left + right) / 2];
    //开始循环，当边界无法严格形成区间时，退出循环
    //while循环的目的是：让比pivot小的值全部移动到pivot左边
    //比pivot大的值全部移到pivot右边
    while(l < r) {
        //在左边找到一个比pivot大的值
        while(arr[l] < pivot) {
            l += 1;
        }
        //在右边找到一个比pivot小的值
        while(arr[r] > pivot) {
            r -= 1;
        }
        //如果l >= r，说明pivot左边的值已经全部小于等于pivot
        //右边的值全部大于等于pivot
        if(l >= r) {
            break;
        }
        //使用一个临时变量，交换
        temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
        //如果交换后发现arr[l] = pivot
        if(arr[l] == pivot) {
            r -= 1;
        }
        if(arr[r] == pivot) {
            l += 1;
        }
    }
    //如果l == r，必须让l ++
    if(l == r) {
        l += 1;
        r -= 1;
    }
    //向左递归
    if(left < r) {
        quickSort(arr,left,r);
    }
    if(right > l) {
        quickSort(arr,l,right);
    }
}