Java 冒泡排序

冒泡排序

• 冒泡排序由嵌套循环完成，并分为外循环和内循环

• 内循环负责比较数组中，两个相邻的元素，如果第一个数比第二个数大，则交换两者的位置，相邻两数依次循环进行比较

• 每完成一次内循环比较（即外循环走完一步）都会产生一个当次内循环最大或者最小的数字并放在数组末尾

• 所以外循环负责将每次内循环中最大或最小的数字放在本次内循环的数组末尾

public static int[] sort(int[] array){
        int tmp = 0;//临时变量
        for (int i = 0; i < array.length-1; i++) {//外循环，当数组只剩最后一个数字没有排序时，此时不再需要排序，所以少一次循环，即length-1
            for (int j = 0; j < array.length-1-i; j++) {//内循环，外循环每走一步，即得出一个最大或最小值放在本次外循环的数字末尾，此时只要对排在最大或最小值前面的数进行比较即可
                if (array[j]>array[j+1]){
                    tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }

        return array;
    }

• 有时候，会遇到程序并没有走完，但是数组已经排序完成，而程序并不知道，此时相当于程序多走了，浪费了资源。这时，我们还可以继续优化代码。我们可以通过添加一个标签flag，当执行了位置交换，证明代码运行了，flag=true。如果这段代码并未运行，则flag=false，此时结束跳出循环。

优化后代码：

public static int[] sort(int[] array){

        int tmp = 0;
        for (int i = 0; i < array.length-1; i++) {//外循环
            boolean flag = false;//要放在外循环中，循环令flag=false，不然经历一次交换位置之后flag=true就没法继续监测接下来的循环
            for (int j = 0; j < array.length-1-i; j++) {//内循环
                if (array[j]>array[j+1]){
                    tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flag = true;
                }
                }
            if (flag=false){//证明这一步整个内循环都没有进行位置交换，即数组已经排序完成，结束循环
                    break;
            }
        }

        return array;
    }