题解 | #冒泡排序+优化#

冒泡排序：依次比较数组中相邻两元素，它们两两比较完成就是一轮冒泡，一轮冒泡后最大的元素排在最后，同时不断重复这一过程

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] arr = new int[7];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }
        scanner.close();

        //write your code here......
        bubbleSort_v2(arr);

        for (int k = 0; k < arr.length; k++) {
            System.out.print(arr[k] + " ");
        }
    }
    private static void bubbleSort_v2(int[] nums) {
        int n = nums.length - 1;
        while (true) {
            int last = 0; // 优化2：记录最后一次交换的为知
            // 优化1：-j 可以减少内部循环的次数
            for (int i = 0; i < n; i++) {
                if (nums[i] > nums[i + 1]) {
                    int temp = nums[i];
                    nums[i] = nums[i + 1];
                    nums[i + 1] = temp;
                    last = i; // 记录上次发生交换的位置
                }
            }
            n = last;
            if (n == 0) {
                break;
            }
        }
    }
}

优化：每轮冒泡，记录最后一次发生交换的最小索引值以以作为下次冒泡的次数，若值为0代表数组是有序的，直接退出外层循环

    private static void bubbleSort(int[] nums) {
        for (int j = 0; j < nums.length - 1; j++) {
            // 【优化II】记录是否发生交换
            boolean swapped = false;
            // 【优化I】减少不必要的比较次数
            for (int i = 0; i < nums.length - 1 - j; i++) {
                System.out.println("一轮下来比较次数：" + i);
                if (nums[i] > nums[i + 1]) {
                    int temp = nums[i];
                    nums[i] = nums[i + 1];
                    nums[i + 1] = temp;

                    swapped = true;
                }
            }
            System.out.println("一轮：" + Arrays.toString(nums));
            if (!swapped) {
                break;
            }
        }
    }