冒泡排序代码优化进阶

冒泡排序

英文名称：bubbleSort

算法思想

把相邻的元素两两进行比较，当一个元素大于右侧相邻元素时，交换他们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。

算法特点

冒泡排序属于交换排序的一种，他是稳定排序。

算法分析

由于该算法每一轮都要遍历所有元素，一共遍历（元素个数 - 1）轮，所以平均时间复杂度为O（N^2）

算法实现

基础版

	/**
     * 冒泡排序基础版
     * @param arr
     */
    private static void bubbleSortOne(int[] arr){
        // 外层循环控制比较轮数 即 数组元素-1 轮
        for (int i = 0;i < arr.length - 1; i++){
            // 内层循环进行每一轮的比较 因为每一轮确定一个元素位置所以只需比较到arr.length - i - 1
            for (int j = 0; j < arr.length - i - 1; j++){
                // 如果前一个数比后一个数大，交换
                if (arr[j] > arr[j + 1]){
                    swap(arr, j, j + 1);
                }
            }
        }
    }

优化版

	/**
     * 冒泡排序优化版
     * 优点：假如进行第四轮比较时已经有序，可以跳出循环停止排序
     * @param arr
     */
    private static void bubbleSortTwo(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        boolean flag; //设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
        for (int i = 0; i < arr.length; i++){
            // 注意需要在每一轮循环都将flag设置为true
            flag = true;
            for (int j = i + 1; j < arr.length; j++){
                if (arr[j] < arr[i]){
                    swap(arr,i,j);
                    // 一旦有交换行为，说明数组并不是有序数组，需要进行继续比较
                    flag = false;
                }
            }
            // 如果一轮比较下来没有进行交换行为，说明此时数组已经有序，直接跳出外层循环返回
            if (flag){
                return;
            }
        }
    }

进阶版

	 /**
     * 冒泡排序进阶版
     * 优点：解决当数组后半部分已经有序时，不再进行比较
     * @param arr
     */
    private static void bubbleSortThree(int[] arr){
        // 记录最后一次进行交换的元素位置
        int lastExchangeIndex = 0;
        // 记录无序数列的边界，每次只需要比较到这里即可
        int sortBorder = arr.length - 1;
        //设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
        boolean flag;

        for (int i = 0; i < arr.length - 1; i++){
            flag = true;
            // 此时已经无需再进行比较到最后一个元素了 只需比较到sortBorder无序边界即可
            for (int j = 0; j < sortBorder; j++){
                if (arr[j] > arr[j + 1]){
                    // 交换元素
                    swap(arr, j, j + 1);
                    // 一旦有交换行为，说明数组并不是有序数组，需要进行继续比较
                    flag = false;
                    // 此时更新为最后一次交换元素的位置
                    lastExchangeIndex = j;
                }
            }
            // 一轮比较后将无序边界更新为最后一次交换元素的位置
            sortBorder = lastExchangeIndex;
            if (flag){
                return;
            }
        }
    }

演化版

/**
     * 冒泡排序演进版 =》 鸡尾酒排序
     * 适用场景：arr = {2,3,4,5,6,7,8,1}
     * 特点：分奇数、偶数轮排序，奇数轮排序可从左至右比较，则偶数轮从右至左比较排序
     * @param arr
     */
    private static void bubbleSortFour(int[] arr){
        // 因为分奇偶次排序，只需进行正常轮数（数组元素 - 1）的一半
        for (int i = 0; i < arr.length / 2; i++) {
            // 有序标记，每轮需设置为true
            boolean flag = true;
            // 然后分为奇数轮 和 偶数轮
            // 奇数轮比较 从左至右比较排序
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]){
                    swap(arr, j, j + 1);
                    flag = false;
                }
            }
            if (flag){
                return;
            }
            // 重新设置flag有序标志
            flag = true;
            // 偶数轮从右至左比较排序
            for (int j = arr.length - i- 1; j > i ; j--) {
                // 注意这里是第j个元素与之前一个所以是j - 1
                if (arr[j] < arr[j - 1]){
                    swap(arr, j, j - 1);
                    flag = false;
                }
            }
            if (flag){
                return;
            }
        }
    }

微信关注

WeChat