java算法篇(一)：冒泡排序

矫情吗；* 2022-11-12 12:55 110阅读 0赞

排序算法是java中的基础算法，很多面试题中都会涉及，今天就来介绍一下冒泡排序：

有一个int数组：int srcArray\[\] = \{3,50,20,95,30,101,78,17,28,21,81,11,32,23\}，将其从小到大排序并输出。

分析：冒泡排序的原理是两两比较，比如，第一次排序，先比较3、50，不用调换顺序；循环再比较50、20，需要调换顺序，这时候数组就是这样：\{3,20,50,95,30,101,78,17,28,21,81,11,32,23\}；循环再比较50、95，以此类推，第一次排序之后，就会确定出最大的一个数并放在末尾。整个循环需要进行数组长度减一次，就能完全排序出来。下面我们看代码案例：

public static void bubbleSort(int[] arr){
            for (int i = arr.length; i > 0; i--) {      //外层循环移动游标
                for(int j = 0; j < i && (j+1) < i; j++){    //内层循环遍历游标及之后(或之前)的元素
                    if(arr[j] > arr[j+1]){
                        int temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                        System.out.println("Sorting: " + Arrays.toString(arr));
                    }
                }
            }
        }

这是全部循环，需要循环arr.length-1次，有些场景我们不需要全部循环arr.length-1次，就能得到想要的结果，因此优化如下：

public static void myBubbleSort(int[] arr){
            int temp = 0;
            boolean bl = false;
            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]){
                        bl = 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(!bl){
                    break;
                }else {
                    bl = false;
                }
            }
    
        }

这个排序就会在第11次结束，并且得到我们想要的结果。