冒泡排序优化算法

依次比较相邻两个元素的大小，如果a[i]>a[i+1],则交换元素，两两都比较一遍为一轮冒泡，结果让最大元素排在最后。

private static void bubbleSort(int[] arr) {
        for (int i=0;i< arr.length-1;i++){
            for (int j = 0; j < arr.length - 1; j++) {
                if (arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
            System.out.println(Arrays.toString(arr));
        }

    }

    private static void swap(int[] arr, int j, int i) {
        int t=arr[j];
        arr[j]=arr[i];
        arr[i]=t;

    }

1. 每轮比较 最后一位肯定是已经排好了，每轮比较次数依次-1

       private static void bubbleSort(int[] arr) {
           for (int i=0;i< arr.length-1;i++){
           	//每轮比较次数-1
               for (int j = 0; j < arr.length - 1 - i; j++) {
                   if (arr[j]>arr[j+1]){
                       swap(arr,j,j+1);
                   }
               }
               System.out.println(Arrays.toString(arr));
           }
       }
   
   

2. 判断数组有序后提前退出循环，判断是否发生交换

       private static void bubbleSort(int[] arr) {
           for (int i=0;i< arr.length-1;i++){
               boolean swapped=false;//判断是否发生交换
               for (int j = 0; j < arr.length - 1 - i; j++) {
                   if (arr[j]>arr[j+1]){
                       swap(arr,j,j+1);
                       swapped=true;
                   }
               }
               System.out.println(Arrays.toString(arr));
               if(!swapped){
                   break;
               }
           }
       }
   

3. 保留每轮最后发生交换元素的索引，索引后面的元素都已经有序。如果索引为0，代表整个数组都有序，退出循环。

       private static void bubbleSortV2(int[] arr) {
           int n= arr.length-1;//每轮比较次数
           int i=0;//记录比较轮数
           do {
               int last = 0;//最后一次交换的索引位置
               for (int j = 0; j < n; j++) {
                   System.out.println("比较第" + j + "次");
                   if (arr[j] > arr[j + 1]) {
                       swap(arr, j, j + 1);
                       last = j;
                   }
               }
               n = last;
               System.out.println("第" + (i++) + "轮" + Arrays.toString(arr));
           } while (n != 0);
       }