1.冒泡排序：

基本思想：交换相邻的两个元素，每次把最大的元素放在后面。

与插入排序和选择排序的区别：

  • 选择排序：遍历数组，如果当前的 index 大于 index + 1, 则互换，然后再让前面的部分进行排序
  • 插入排序：以index 为起点，遍历 data.length - index ，将最大值放到最后(不是相邻两元素进行比较)
  • 时间复杂度均为O(n^2)

    2.冒泡排序的实现：

    ```java // 两元素进行交换，最后将最大值放在最后 // 进行完一次循环后，下一次循环为[0, data.length - i - 1] 区间 public void BubbleSort(E[] arr){ for(int i = 0 ; i < data.length; i++){
    1.   for(int j = 0 ; j < data.length - 1 - i; j++){
    2.       if(data[j] < data[j + 1]){
    3.           swap(arr, j , j + 1);
    4.       }
    5.   }
    } }

// 优化，记录交换，假如在某次遍历中一次交换都没有进行，则证明已经处于有序状态 public void BubbleSort(E[] arr){ Boolean isSwapped = true; for(int i = 0 ; i < data.length; i++){ for(int j = 0 ; j < data.length - 1 - i; j++){ if(data[j] > data[j + 1]){ swap(arr, j , j + 1); isSwapped = false; } } if(isSwapped) break; } }

// 假如最后一次交换的位置在 j 的前面， 则下一次交换的区间更改为该位置 public void BubbleSort(E[] arr){ // i 表示循环次数 for(int i = 0 ; i < arr.length;){ int swapped = 0; for(int j = 0; j < data.length - 1 -i ; j++){ if(data[j] > data[j+1]){ swap(arr, j , j + 1); swapped = j + 1; } } i = arr.length - swapped; } }

<a name="mjhqk"></a>
## 3.冒泡排序的优化：
冒泡排序实际上是减少逆序对的过程，对于部分有序的数组，冒泡排序与插入排序一样，能变成一个O(n)级别的算法。
<a name="ZhX9G"></a>
## 4.从后往前实现冒泡法
```java
public static <E extends Comparable<E>> void sort3(E[] arr) {
        // 相邻元素进行交换，每次循环之后，最前面那个为最小值
        // 每循环一次 ，若循环 i 次 ， 下一轮循环遍历的区间为 [0,data - i - 1]
       public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0 ; i < arr.length - 1; i++) {
            for (int j = arr.length - 1; j > i ; j--) {
                if (arr[j].compareTo(arr[j - 1]) < 0) {
                    swap(j,j - 1, arr);
                }
            }
        }
    }
    }