排序算法之冒泡排序及其优化

小咪咪 2022-11-02 11:40 209阅读 0赞

>     冒泡排序：
>      * 依次取出数组中的每个元素，将此元素与其之后的每个元素比较，若大于其后的元素，则交换位置
>      双重循环：
>      * 外层循环：获取每次遍历的最大值
>      * 内层循环：遍历该元素后的每一个元素，与当前元素比较大小，若当前元素大，则交换位置
>      O(n²)  稳定

/**
         * 冒泡排序：
         * 依次取出数组中的每个元素，将此元素与其之后的每个元素比较，若大于其后的元素，则交换位置
         * 双重循环：
         * 外层循环：获取每次遍历的最大值
         * 内层循环：遍历该元素后的每一个元素，与当前元素比较大小，若当前元素大，则交换位置
         * O(n²)  稳定
         */
        static void bubbleSort(int[] array) {
            for (int i = array.length - 1; i > 0; i--) {
                for (int j = 0; j < i; j++) {
                    if (array[j] > array[j + 1]) {
                        int temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                    }
                }
            }
        }

>     冒泡算法优化。
>      即最优时间复杂度为O(n)。即外层循环执行一次，内层循环执行n次。
>      * 在进入外层循环时给一个标记flag=true，若在内层循环中进入了if判断条件，则将此标记的值改为false，
>      * 每次内层循环结束后判断flag的值，若此值为true时，结束外层循环。
>      * 至此，外层循环只执行一次，内层循环执行了n次，时间复杂度为O(n)

static void bubbleSortPlus(int[] array) {
            for (int i = array.length - 1; i > 0; i--) {
                boolean flag = true;
                for (int j = 0; j < i; j++) {
                    if (array[j] > array[j + 1]) {
                        int temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                        flag = false;
                    }
                }
                if (flag) {
                    break;
                }
            }
        }