博客

冒泡排序思想

1. 比较相邻的两个元素，如果第一个元素大于第二个元素，就交换位置
2. 对每一对相邻的元素再做同样的比较，从最开始的一对到结尾的一对完成全部的比较。最后一个元素肯定最大的
3. 对剩下的元素重复第二步操作，直到只有一个元素为止

两个数交换值

int a = 5;
int b = 10;
int c = a;//c = 5
a = b;//a = 10
b = c;//b = 5

模拟冒泡排序

//模拟冒泡排序
        int[] arr = {11,31,2,56,43,67,43,21};
        //每相邻的元素进行比较大小
        //遍历数组
        // 第1趟  11,2,31,43,56,43,21,[67]     7次
        // 第2趟  2,11,31,43,43,21,[56]        6次
        // 第3趟  2,11,31,43,21,[43]           5次
        // 第4趟  2,11,31,21,[43]              4次
        // 第5趟  2,11,21,[31]                 3次
        // 第6趟  2,11,[21]                    2次
        // 第7趟  2,[11]                       1次
 
        //分析：
        //   共比较趟数  arr.length-1
        //   每一趟中比较的次数： 趟数+次数 = 8(arr.length)
        //   两个变量互换值
        //System.out.println(Arrays.toString(arr));
        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]){
                    int t = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = t;
                }
            }
            System.out.println(Arrays.toString(arr));
        }

冒泡排序的优化

for (int i = 0; i < arr.length - 1; i++) {//控制趟数
            //定义boolean类型变量,用来标识每趟是否存在交换值
            boolean flag = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {//控制次数
                //比较相邻元素的值
                if(arr[j] > arr[j+1]){
                    int t = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = t;
                    flag = true;//说明这趟存在交换值情况
                }
            }
            System.out.println(Arrays.toString(arr));
            if(!flag){ //取反
                break;//若flag为false,表示此趟不存在交换值的情况,提前结束循环
            }
        }