冒泡排序：两两比较相邻的元素，如果反序则交换，直到没有反序记录为止
最优时间复杂度 冒泡排序 - 图1, 最坏时间复杂冒泡排序 - 图2

代码

  1. /**
  2.  * @Description: 冒泡排序：两两比较相邻的元素，如果反序则交换，直到没有反序记录为止
  3.  * 最优时间复杂度 O(n), 最坏时间复杂度 O(n2)
  4.  * @Author: lizhouwei
  5.  * @CreateDate: 2018/6/23 8:34
  6.  */
  7. public class BubbleSort {
  9.     public static void bubbleSort(Integer[] arr) {
  10.         if (arr == null || arr.length == 0) {
  11.             return;
  12.         }
  13.         SortUtil.printArray("冒泡排序前", arr);
  14.         boolean flag = true;
  15.         for (int i = 1; i < arr.length && flag; i++) {
  16.             flag = false;
  17.             for (int j = arr.length - 1; j >= i; j--) {
  18.                 if (arr[j] < arr[j - 1]) {
  19.                     SortUtil.swap(arr, j, j - 1);
  20.                     flag = true;
  21.                 }
  22.             }
  23.         }
  24.         SortUtil.printArray("冒泡排序后", arr);
  25.     }
  27. }

冒泡复杂度分析

时间复杂度：
当最好的情况，也就是要排序的表本身就是有序的，那么只需要n-1次比较，没有数据交换，时间复杂度为冒泡排序 - 图3,
当最坏的情况，即要排序的表是你须得情况，此时需要比较
冒泡排序 - 图4次，因此时间复杂度为 冒泡排序 - 图5；