算法排序之冒泡排序及优化

public class Bubbling {

    public static void main(String[] args) {
        // 定义需要排序的数组
        int[] arr = {0,1,21,2,31,12,5,8};
        // 冒泡排序方法
        bubbleSort(arr);
        bubbleOptSort(arr);
    }


    /**
     * 冒泡排序
     * @param arr 数组
     */
    public static void bubbleSort(int[] arr){
        // i=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]) {
                    // 交换arr[j+1]和arr[j]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.println("第"+(i+1)+"轮排序结果" + Arrays.toString(arr));
        }
        System.out.println("冒泡排序最终结果" + Arrays.toString(arr));
    }

    /**
     * 冒泡排序优化
     * 冒泡排序的一个优化点是在某次遍历中没有发生任何交换时，说明数组已经是有序的，可以提前终止排序。
     * 这种优化可以显著减少不必要的比较和交换操作，特别是在数组接近有序或已经有序的情况下。
     * @param arr 数组
     */
    public static void bubbleOptSort(int[] arr){
        for (int i = 0; i< arr.length - 1;i++){
            // 在最外层循环定义一个用于判断是否发生交换的标志变量
            boolean flag = true;
            for (int j = 0; j< arr.length-1-i; j++){
                // 比较两个数，如果后面的大于前面的，则进行交换
                if (arr[j] > arr[j+1]){
                    int temp =  arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    // 发生交换，修改标记
                    flag = false;
                }
            }
            if (flag){
                break;
            }
            System.out.println("第"+(i+1)+"轮排序结果" + Arrays.toString(arr));
        }
        System.out.println("冒泡排序优化后最终结果" + Arrays.toString(arr));
    }
    
}

对比两次执行结果

优化前：

优化后：