冒泡排序

基本思想

• 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。
• 直观表达，每一趟遍历，将一个最大的数移到序列末尾。

描述

• 比较相邻的元素，如果前一个比后一个大，交换之。
• 第一趟排序第1个和第2个一对，比较与交换，随后第2个和第3个一对比较交换，这样直到倒数第2个和最后1个，将最大的数移动到最后一位。
• 第二趟将第二大的数移动至倒数第二位
  ......

public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {3, 9, -1, 10, -2};
        //   int arr[] = {1, 2, 3, 4, 5};

        //时间复杂度O(n²)
        //第一趟排序 就是将最大的数排在最后
        int temp = 0; //临时变量 用于交换
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                if (arr[i] > arr[i + 1]) {
                    temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
            System.out.println("排序后的结果");
            System.out.println(Arrays.toString(arr));
        }

    }
}

冒泡排序优化

优化一（优化外层循环）

　若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，因此，冒泡排序过程可在此趟排序后终止。为此，在下面给出的算法中，引入一个标签flag，在每趟排序开始前，先将其置为false。若排序过程中发生了交换，则将其置为true。各趟排序结束时检查flag，若未曾发生过交换则终止算法，不再进行下一趟排序。

优化二（优化内层循环）

​ 记下最后一次交换的位置，后边没有交换，必然是有序的，然后下一次排序从第一个比较到上次记录的位置结束即可。

public class BubbleSort{
    public static void main(String[] args) {
        int arr[] = {3, 9, -1, 10, -2};
        int length = arr.length;
        bubble(arr,length);
    }
    public static void bubble(int arr[],int length){
        //第一趟排序 就是将最大的数排在最后
        int temp = 0; //临时变量 用于交换
        boolean flag = false; //标识变量表示是否进行过交换
        int tempPosition = 0; // 记录最后一次交换的位置
        int len = length-1;
        for (int j = 0; j < arr.length-1; j++) {
            for (int i = 0; i < len; i++) {
                if (arr[i] > arr[i + 1]) {
                    flag = true;
                    tempPosition = i;  //记录交换的位置
                    temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
            len = tempPosition;//把最后一次交换的位置给len，来缩减内循环的次数
            System.out.println("排序后的结果");
            System.out.println(Arrays.toString(arr));
            if (!flag){
                break; //一次交换都没有发生
            }
            else {
                flag = false; //重置flag 进行下次判断
            }
        }
    }
}