java冒泡排序算法及其优化

冒泡排序是常用的排序算法，时间复杂度

• 最坏情况，为O(n²)
• 最好情况，为O(n)

此外，空间复杂度O(1)，稳定

基本思想

（设 k = n, 这里的 n 表示序列长度)

从左侧第一个元素开始到n-1个元素结束，每个元素依次和右侧相邻元素组成一对

从左到右依次比较每对元素的值，如果不符合排序规则，则元素交换，直到交换完最后一对，以上过程称为一趟。

每趟结束后，最后一个有序，去掉最后一个( 即n=n-1)，继续下一趟，直到n==1结束

（易知需要 k-1 趟）

代码实现

分析每趟需要几组？

第一趟需要n-1组，第二趟需要n-2组，设有 i 从0开始，则每趟有 n-1-i 组

以数组为例，容易得出以下基本算法（需要优化）

    public static void main(String []args){

        int[] arr = {6,4,2,9,88,55};
        System.out.println("排序前："+Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("排序后："+Arrays.toString(arr));
    }
    /**
     * 冒泡排序
     * @param arr 原数组
     */
    static void bubbleSort(int[] arr){

        int temp;  // 临时变量
        for (int i = 0; i < arr.length-1; i++) {  // n-1趟
            for (int j = 0; j < arr.length-1-i; j++) {  // n-1-i组

                // >:升序  <:降序
                if(arr[j]<arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }

        }

    }

程序运行结果：

• 排序前：[6, 4, 2, 9, 88, 55]
• 排序后：[88, 55, 9, 6, 4, 2]

冒泡算法优化

我们知道，冒泡算法是 ”相邻替换“实现的，那么如果第一趟没有发生替换是不是说明序列本身有序呢？

所以，在程序中，对每一趟增加替换检测即可

优化后，时间复杂度最好的情况下能达到O(n)

    public static void main(String []args){

        int[] arr = {55, 88, 9, 6, 2, 4};
        System.out.println("排序前："+Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("排序后："+Arrays.toString(arr));
    }
    /**
     * 冒泡排序
     * @param arr 原数组
     */
    static void bubbleSort(int[] arr){

        int temp;  // 临时交换变量
        boolean changeFlag;  // 交换检测变量

        for (int i = 0; i < arr.length-1; i++) {  // n-1趟
            changeFlag = false;
            for (int j = 0; j < arr.length-1-i; j++) {  // n-1-i组

                // >:升序  <:降序
                if(arr[j]<arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    changeFlag = true;  // 发生交换         
               }
            }

            if(!changeFlag){  // 一趟中没有交换
                break;
            }

        }

    }

程序执行结果：

• 排序前：[55, 88, 9, 6, 2, 4]
• 排序后：[88, 55, 9, 6, 4, 2]