排序--冒泡排序

1、什么是冒泡排序?

就是把一个无序数组内的元素，从头开始，两两比较并交换位置，直到把最大（最小）的一位放置在队尾

2、代码原理：

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤1~3，直到排序完成。

3、代码实现

public class ArrSort {
    public static void main(String[] args) {
        int[] arr={3,9,-1,10,20};
        int temp=0;
        for (int j=0;j<arr.length-1;j++){
            //第i遍
            for (int i=0;i<arr.length-1-j;i++){
                if (arr[i]>arr[i+1]){ //左边元素比右边大就交换位置
                    temp=arr[i];
                    arr[i]=arr[i+1];
                    arr[i+1]=temp;
                }
            }
            System.out.println("第"+j+"次排序");
            System.out.println(Arrays.toString(arr));

        }
    }
}

4、优化

按照上述的代码，每次排序都要进行arr.length-1轮，但是有可能前面几轮就已经达到排序好的效果，后面做的就是无用功

如图第二轮已经达到排序完成的效果，怎么优化？

加一个判定条件，如果没有发生元素的交换，就说明已经排序完成了

public class ArrSort {
    public static void main(String[] args) {
        int[] arr={3,9,-1,10,20};
        int temp=0;
        //设置一个开关
        boolean flag=false;
        for (int j=0;j<arr.length-1;j++){
            //第一遍

            for (int i=0;i<arr.length-1-j;i++){
                if (arr[i]>arr[i+1]){  //发生元素交换就置为true，这一轮完成后再判断
                    flag=true;
                    temp=arr[i];
                    arr[i]=arr[i+1];
                    arr[i+1]=temp;
                }
            }
            if (flag){  //说明发生了元素交换，继续进行下一轮
                System.out.println("第"+j+"次排序");
                System.out.println(Arrays.toString(arr));
                flag=false;   //再把flag置为初始值
            }else{  //没有进行元素交换，就跳出循环条件，排序完成
                System.out.println("排序结束");
                break;
            }
        }
    }
}

5、时间复杂度

由上述代码可发现，冒泡排序是用了双层for循环，所以O（n^2）