三大基础排序 -选择排序、冒泡排序、插入排序

排序算法

排序算法，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。一般默认排序是按照由小到大即升序排列。

冒泡排序

冒泡排序（Bubble Sort）简单的基于比较的排序算法。每次比较相邻两个元素，如果他们的顺序错误就把他们交换过来。由于较大的数据会不断地向上”冒“，所以以冒泡排序命名。

算法步骤

• 从头开始，比较相邻元素，如果顺序不对，就交换。
• 每次选出一个局部最大值
• 走过n - 1 趟后，数组就有序了

动图

代码

public class P02_BubbleSort {
    public static void bubbleSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }

        for(int i = 0;i < arr.length - 1;i++) {
            for(int j = 0;j < arr.length - 1 - i;j++) {
                if(arr[j] > arr[j + 1]) {
                    swap(arr,j,j + 1);
                }
            }
        }
    }

    public static void swap(int[] arr,int i,int j) {
        int t = arr[i];
        arr[i] = arr[j];
         arr[j] = t;
    }

    public static void main(String[] args) {
        int[] arr = {9,8,7,6,5,4,3,2,1};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
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

优化

 public static void bubbleSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }

        for(int i = 0;i < arr.length - 1;i++) {
        	boolean success = false; 
            for(int j = 0;j < arr.length - 1 - i;j++) {
                if(arr[j] > arr[j + 1]) {
                    swap(arr,j,j + 1);
                    success = true;
                }
            }
            if(success == false) {
            	break;// 已经有序
            }
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

总结

冒泡排序的时间复杂度$O(N)$，空间复杂度$O(1)$，冒泡排序是一种性能比较差的排序，如果不优化，那么无论是何种数据状况，都要经理$N^2$次比较。冒泡排序大量浪费比较行为，每趟比较只会选择出一个最大值，所以性能较差。

选择排序

选择排序是一种简单直观的基于比较的排序算法，性能不受数据状况的左右，就算是已经有序的数据，也是$O(N^2)$的时间复杂度。

算法步骤

（不用交换的没有画出）

• 0 ~ n - 1 范围 找到最小值 交换到 0 位置
• 1 ~ n - 1 范围 找到最小值 交换到 1 位置
• 2 ~ n - 1 范围 找到最小值 交换到 2 位置
• … …
• n - 2 ~ n - 1 范围找到较小值 交换到 n - 2 位置
• 排序完成

动图

代码

package package01;

import java.util.Arrays;

public class P01_SelectSort {
    public static void selectSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;

        }
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[minIndex] < arr[j] ? minIndex : j;
            }
            swap(arr, minIndex, i);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
        int[] arr = {9,8,7,6,5,4,3,2,1};
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
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

总结

选择排序也是一种性能较差的排序算法，性能不受数据状况左右，大量浪费比较行为。

插入排序

插入排序就像打扑克时拿牌一样，一张一张将扑克牌放到对应的位置，也是一个基于比较的排序。只是插入排序受数据状况影响，当数据状况趋于有序时，插入排序的速度会非常快，趋于$O(N)$，但是时间复杂度是最坏情况，所以插入排序的时间复杂度是$O(N^2)$.

算法步骤

就如上述数据，我们要将这组数字从小到大进行排列。从左往右依次考虑每个数字，让这个数字左边局部有序，考虑完整个数据就有序了。

• 考虑前 $1$ 个数 已经有序
• 考虑前 $2$ 个数，如果前面的数据大于当前数则交换，做到局部有序
• 考虑前 $3$ 个数，如果前面的数据大于当前数则交换，做到局部有序
• … …
• 考虑前 $n-1$ 个数，如果前面的数据大于当前数则交换，做到局部有序
• 完成排序

动图

代码

package package01;

import java.util.Arrays;

public class P03_InsertSort {
    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);
            }
        }
    }
    public static void swap(int[] arr,int i,int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    public static void main(String[] args) {
        int[] arr = {0,9,8,7,6,5,4,3,2,1};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));

    }
}
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

总结

插入排序的常数时间要优于选择排序和插入排序，但是其时间复杂度仍然是$O（N^2）$