冒泡排序算法并调优

算法步骤

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

• 针对所有的元素重复以上的步骤，除了最后一个。

• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

• 一共进行了数组元素个数-1次大循环，且每次大循环中需要比较的元素越来越少。

• 优化：如果在某次大循环，发现没有发生交换，则证明已经有序。

代码

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {2, 6, 1, 5, 3, 4};
        System.out.println("冒泡排序前的数组: "+Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("冒泡排序后的数组: "+Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr){
        int temp = 0;//用来交换的临时变量
        boolean flag = 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]){
                    flag = true;//发生了交换，标识改为true
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            if (!flag){//如果没有发生交换就会直接退出循环
                break;
            }else {//发生交换后把flag重置为false
                flag = false;
            }
        }
    }
}