最坏 平均 时间复杂度 ：O (n^2)
    最好时间复杂度： O (n)
    空间复杂度： O (1)

    排序算法的稳定性：
    如果相等的两个元素，在排序前后的相对位置保持不变，那么就是稳定的排序算法

    image.png

    冒泡排序：

    1. for (int i = arr.length - 1; i >= 0; i--) {
    2.             for (int j = 0; j < i; j++) {
    3.                 if (arr[j] > arr[j + 1]) {
    4.                     int temp = arr[j];
    5.                     arr[j] = arr[j + 1];
    6.                     arr[j + 1] = temp;
    7.                 }
    8.             }
    9.         }

    用boolean判断是否有序

    1. for (int i = arr.length - 1; i >= 0; i--) {
    2.             boolean sorted = true;
    3.             for (int j = 0; j < i; j++) {
    4.                 if (arr[j] > arr[j + 1]) {
    5.                     int temp = arr[j];
    6.                     arr[j] = arr[j + 1];
    7.                     arr[j + 1] = temp;
    8.                     sorted = false;
    9.                 }
    10.             }
    11.             if (sorted) {
    12.                 //说明有序的
    13.                 break;
    14.             }
    15.         }

    用一个int变量记录索引

    1. for (int i = arr.length - 1; i >= 0; i--) {
    2.             //初始值为完全有序做个准备
    3.             int sortIndex = 0;
    4.             for (int j = 0; j < i; j++) {
    5.                 if (arr[j] > arr[j + 1]) {
    6.                     int temp = arr[j];
    7.                     arr[j] = arr[j + 1];
    8.                     arr[j + 1] = temp;
    9.                     sortIndex = j;
    10.                 }
    11.             }
    12.             i = sortIndex;
    13.         }

    图片理解：
    bubbleSort