算法思想

1.比较相邻的两个元素，交换较大的元素到右边
2.每次循环比较相邻的两个元素，直到最后一对，最后的元素应该是最大数
3.针对所有的元素重复以上的步骤，除了最后一个
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

代码

public static void bubbleSort(int[] arr) {
        //外层循环控制排序趟数
        for (int i = 0; i < arr.length - 1; i++) {
            //标识控制  当数组完全有序 时间复杂度可为o(n)
            //如果这一趟发生了交换，则为true，否则为false，如果有一趟没有发生交换，说明排序已经完成
            boolean flag = false;
            //内层循环控制每一趟排序多少次
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }

时间复杂度

1.如果是正序，通过设置标识只外层需要循环一次，比较次数为n-1，所以冒泡排序的最好的时间复杂度为O(N)
2.如果是反序的，则需要进行n-1次循环，要进行n-i次比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
比较次数 C = n(n-1)/2 = O(n^2)
移动次数M = 3n*(n-1)/2 = O(n^2)
3.冒泡排序总的平均时间复杂度为O(n^2)