1.冒泡排序(Bubble Sort)

1.1 动画展示

示例

1.2 思路分析

冒泡排序(Bubble Sorting)的基本思想是:通过对待排序序列从前向后(从下标较小的元素开始)，依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向. 上冒。
优化:因为排序的过程中，各元素不断接近自己的位置，如果-趟比较下来没有进行过交换,就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排序写好后，在进行)

1.3演示冒泡排序的例子（图解）

小结上面的图解过程:(1)一共进行数组的大小-1次大的循环
(2)每一趟排序的次数在逐渐的减少
(3)如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序。这个就是优化

1.4 复杂度分析

1.不管原始数组是否有序，时间复杂度都是O（n2），
因为没一个数都要与其他数比较一次，（n-1）2次，分解：n2-2n+1, 去掉低次幂和常数，剩下n2,所以最后的时间复杂度是n2
2.空间复杂度是O（1）,因为只定义了两个辅助变量，与n的大小无关，所以空间复杂度为O（1）

1.5 java代码实现

最近看的
初始优化，若发现没有有一轮没发生交换，则退出循环

public static void Bubble2(int[] arr){
        for (int i = 0; i <arr.length-1 ; i++) {
            boolean swapped=false;//是否发生了交换 
            //注意：swapped 在第一层for循环里定义，如果在外层for循环，后面还要多加一个判断
            //如在下下面的优化
            for (int j = 0; j <arr.length-i-1 ; j++) {
                System.out.println((j+1)+"次");
                if (arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    swapped =true;
                }
            }
            System.out.println(Arrays.toString(arr));
            //一轮都没有进行交换过，说明数组排序完，则终止循环
            if (!swapped){
                break;
            }
        }
    }

二次优化
记录最后交换的位置,直到最后交换的位置为0，交换结束。

 public static void Bubble(int[] arr){
        int n = arr.length-1;//需要比较的最后一个索引
        while (true){
            int last = 0;//记录最后交换的位置
            for (int i = 0; i < n; i++) {
                System.out.println("比较次数:"+(i+1));
                if (arr[i]>arr[i+1]){
                    swap(arr,i,i+1);
                    last=i;//更新最后交换的位置
                }
            }
            n =last;//更新最后需要比较的索引,n其实就是要比较的次数
            System.out.println("第轮冒泡"+Arrays.toString(arr));
            if (n==0){
                break;
            }
        }
    }

之前看的
未优化

public class BubbleSort {
    public static void main(String[] args) {
       int arr[] = new int[]{1,2,3,4,5,0};
        //冒泡排序时间复杂度为O(n^2)，给80000个数据，测试
        //创建80000个随机的数组
//        int[] arr =new int[80000];
//        for (int i=0;i<80000;i++){
//            arr[i] = (int) (Math.random() * 8000000);//生成一个[0,8000000)数
//        }
//        Date date1 = new Date();
//        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
//        String date1Str = simpleDateFormat.format(date1);
//        System.out.println("排序前的时间是="+date1Str);
//
        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr));
        System.out.println("进行冒泡排序：");
        BubbleSort2(arr);
//        Date date2 = new Date();
//        String date1Str2 = simpleDateFormat.format(date2);
//        System.out.println("排序前的时间是="+date1Str2);
//        System.out.println(Arrays.toString(arr));
    }
    }
    /**
     * 未优化
     * @param arr
     */
    public static void BubbleSort(int[] arr){
            int temp=0;
            for (int i = 0; i<arr.length-1;i++){
                for (int j=0 ;j<arr.length-1-i;j++){
                    if (arr[j]>arr[j+1]) {  //逆序则改变该处符号即可
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
//                System.out.println("第"+(i+1)+"次冒泡排序");
//                System.out.println(Arrays.toString(arr));
            }
    }
}

优化代码：

 /**
     * 优化后，如果有一次未发生交换则停止排序
     * @param arr
     */
    public static void BubbleSort2(int[] arr){
        int temp=0;
        boolean flag = false;//标识变量，表示是否交换过 true表示发生过交换
        for (int i = 0; i<arr.length-1;i++){  //需要进行arr.length-1趟冒泡
            for (int j=0 ;j<arr.length-1-i;j++){  //每一趟找最后的最大值。
                if (arr[j]>arr[j+1]) {  //逆序则改变该处符号即可
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
//            System.out.println("第"+(i+1)+"次冒泡排序");
//            System.out.println(Arrays.toString(arr));
            if (!flag){
                break;//在一趟排序中，一次交换也没发生，则说明是有序，排序完毕，终止循环
            }else {
                flag = false;//重置flag！！！，进行下次判断，如果没加这句，flag的设置相当于无效
            }
        }
    }

推导

        /*
        // 第二趟排序，就是将第二大的数排在倒数第二位
        for (int j = 0; j < arr.length - 1 - 1 ; j++) {
            // 如果前面的数比后面的数大，则交换
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        System.out.println("第二趟排序后的数组");
        System.out.println(Arrays.toString(arr));
        // 第三趟排序，就是将第三大的数排在倒数第三位
        for (int j = 0; j < arr.length - 1 - 2; j++) {
            // 如果前面的数比后面的数大，则交换
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        System.out.println("第三趟排序后的数组");
        System.out.println(Arrays.toString(arr));
        // 第四趟排序，就是将第4大的数排在倒数第4位
        for (int j = 0; j < arr.length - 1 - 3; j++) {
            // 如果前面的数比后面的数大，则交换
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        System.out.println("第四趟排序后的数组");
        System.out.println(Arrays.toString(arr)); */
    }

运行截图