冒泡排序、插入排序、选择排序

三种算法对比：

image.png

冒泡排序

    /**
     * 冒泡排序.
     * <p>
     * 时间复杂度：O(n2)
     * 空间复杂度：O(1)
     *
     * @param a 数组
     * @param n 数组长度
     */
    public static void bubbleSort(int[] a, int n) {
        if (n <= 1) return;

        for (int i = 0; i < n; i++) {
            boolean flag = false;
            // 这里注意n-1,边界问题：数组溢出越界
            for (int j = 0; j < n - 1 - i; j++) {
                if (a[j + 1] < a[j]) {
                    int temp = a[j + 1];
                    a[j + 1] = a[j];
                    a[j] = temp;
                    // 此次有数据交换
                    flag = true;
                }
            }
            if (!flag) return;
        }
    }

    /**
     * 冒泡排序改进.在每一轮排序后记录最后一次元素交换的位置,作为下次比较的边界,
     * 对于边界外的元素在下次循环中无需比较.
     *
     * @param a
     * @param n
     */
    public static void bubbleSort2(int[] a, int n) {
        if (n <= 1) return;

        int tmpBorder = 0;
        int sortBorder = n - 1;
        for (int i = 0; i < n; i++) {
            boolean flag = false;

            for (int j = 0; j < sortBorder; j++) {
                if (a[j + 1] < a[j]) {
                    int tmp = a[j + 1];
                    a[j + 1] = a[j];
                    a[j] = tmp;
                    flag = true;
                    tmpBorder = j;
                }
            }
            sortBorder = tmpBorder;
            // 没有数据交换，提前退出
            if (!flag) return;
        }
    }

插入排序

    /**
     * 插入排序.
     * <p>
     * 时间复杂度：O(n2)
     * 空间复杂度：O(1)
     *
     * @param a 数组
     * @param n 数组长度.
     */
    public static void insertionSort(int[] a, int n) {
        if (n <= 1) return;

        for (int i = 1; i < n; i++) {
            int val = a[i];
            int j = i - 1;
            // 查找要插入的位置并移动数据
            for (; j >= 0; j--) {
                if (a[j] > val) {
                    a[j + 1] = a[j];
                } else {
                    break;
                }
            }
            a[j + 1] = val;
        }
    }

选择排序

    /**
     * 选择排序.
     * <p>
     * 时间复杂度：O(n2)
     * 空间复杂度：O(1)
     *
     * @param a
     * @param n
     */
    public static void selectionSort(int[] a, int n) {
        if (n <= 1) return;

        for (int i = 0; i < n; i++) {
            int minIndex = i;
            int j = i + 1;
            // 查找最小值
            for (; j < n; j++) {
                if (a[minIndex] > a[j]) {
                    minIndex = j;
                }
            }
            // 交换
            int tmp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = tmp;
        }
    }

测试

    public static void main(String[] args) {
        int[] array = {3, 4, 2, 1, 5, 6, 7, 8};
//        bubbleSort(array, array.length);
        bubbleSort2(array, array.length);
//        insertionSort(array, array.length);
//        selectionSort(array, array.length);
        System.out.println(Arrays.toString(array));
    }

提升

冒泡排序和插入排序的时间复杂度都是 O(n2)，都是原地排序算法，为什么插入排序要比冒泡排序更受欢迎呢？

前面分析冒泡排序和插入排序的时候讲到，冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。但是，从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个。

冒泡排序和插入排序在时间复杂度上是一样的，都是 O(n2)，但是如果我们希望把性能优化做到极致，那肯定首选插入排序。