冒泡排序算法

1. 冒泡排序

1.1 概念

• 什么是冒泡排序？

  冒泡排序（Bubble Sort）是一种最基础的交换排序。由于每一个元素都像气泡一样，根据自身大小一点一点向数组的一侧移动，所以叫做冒泡排序。

• 以升序为例，依次比较数组中相邻两个元素的大小，若arr[ i ] > a[ i+1 ]，则交换两个元素，两两都比较一遍成为一轮冒泡，结果是让最大的元素排到数组最后。重复以上的步骤，直到整个数组有序。

• 降序类似，每轮把最小的元素排到数组最后。

• 动画展示（此动画为网上图片，拿来借鉴一下，便于大家理解）

  

1.2 代码演示

• 初步实现冒泡排序

  public class BubbleSort01 {
      public static void main(String[] args) {
          int[] arr = {52, 9, 21, 4, 36, 11, 7, 6};
          bubble(arr);
      }
      
      //冒泡排序方法
      public static void bubble(int[] arr) {
          for (int j = 0; j < arr.length - 1; j++) {
              for (int i = 0; i < arr.length - 1; i++) {
                  if (arr[i] > arr[i + 1]) {
                      swap(arr, i, i + 1);
                  }
              }
              System.out.println("第" + (j + 1) + "次冒泡排序：" + Arrays.toString(arr));
          }
      }
      
      //交换方法
      public static void swap(int[] arr, int i, int j) {
          int t = arr[i];
          arr[i] = arr[j];
          arr[j] = t;
  
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26

• 输出结果：

  

• 可以看到，冒泡排序确实是把每一轮最大的元素排到数组的最后，像冒泡泡一样。

1.3 优化一减少比较次数

• 我们不难发现上述的代码，每一轮 j 循环的时候，都要进行 arr.length -1 次排序。实际上，我们每轮排序好的元素已经不需要再去比较了，这样无疑降低了效率。

• 优化代码

  public class BubbleSort02 {
      public static void main(String[] args) {
          int[] arr = {9, 21, 4, 36, 11, 7, 6};
          bubble(arr);
      }
  
      public static void bubble(int[] arr) {
          for (int j = 0; j < arr.length - 1; j++) {
              //arr.length - 1  =>  arr.length - 1 - j
              for (int i = 0; i < arr.length - 1 - j; i++) {
                  System.out.println("比较次数：" + (i + 1));
                  if (arr[i] > arr[i + 1]) {
                      swap(arr, i, i + 1);
                  }
              }
              System.out.println("第" + (j + 1) + "次冒泡排序：" + Arrays.toString(arr));
          }
      }
  
      public static void swap(int[] arr, int i, int j) {
          int t = arr[i];
          arr[i] = arr[j];
          arr[j] = t;
  
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26

• 输出结果：通过输出每轮比较的次数可以更直观的看到优化效果

  

1.4 优化二：减少冒泡次数

• 试想在这种场景：一个有7个元素的数组，前四轮冒泡就已经将数组排序好了，那剩下的冒泡是无意义的。

• 优化代码

  public class BubbleSort03 {
      public static void main(String[] args) {
          int[] arr = {9, 21, 4, 11, 7, 6, 36, 52};
          bubble(arr);
      }
  
      public static void bubble(int[] arr) {
          for (int j = 0; j < arr.length - 1; j++) {
              //判断是否发生了冒泡
              boolean flag = false;
              //arr.length - 1  =>  arr.length - 1 - j
              for (int i = 0; i < arr.length - 1 - j; i++) {
                  if (arr[i] > arr[i + 1]) {
                      swap(arr, i, i + 1);
                      //如果发生了交换，即这一轮冒泡是有意义的，则把flag设为true
                      flag = true;
                  }
              }
              System.out.println("第" + (j + 1) + "次冒泡排序：" + Arrays.toString(arr));
              if (!flag) {
                  break;
              }
          }
      }
  
      public static void swap(int[] arr, int i, int j) {
          int t = arr[i];
          arr[i] = arr[j];
          arr[j] = t;
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31

• 输出结果：

  

• 可以看到，本来要进行7轮冒泡，在第五轮冒泡确定已经不再发生交换，即数组已经排序好了之后，就不再进行后面的冒泡

1.5 优化三：进一步减少比较次数

• 试想：如果我们第一轮冒泡的时候，后面三个元素就已经排序好了，按照优化一每轮减少 j 次比较的方案，仍有一些非必要的比较。

• 优化代码：每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值为0，表示排序完毕，退出循环。

  public class BubbleSort04 {
      public static void main(String[] args) {
          int[] arr = {9, 21, 4, 11, 7, 6, 36, 52};
          bubble(arr);
      }
  
      public static void bubble(int[] arr) {
          //设置一个临时变量为数组长度-1，用作第一次冒泡的比较次数
          int temp = arr.length - 1;
          while (true){
              //设置该轮冒泡最后一次做交换的索引位置，初始值为0
              int lastIndex = 0;
              //temp为比较次数，第一次为数组长度-1
              for (int i = 0; i < temp; i++) {
                  System.out.println("比较次数：" + (i + 1));
                  if (arr[i] > arr[i + 1]) {
                      swap(arr, i, i + 1);
                      //记录该轮最后一次交换的索引位置
                      lastIndex = i;
                  }
              }
              temp = lastIndex;
              System.out.println(Arrays.toString(arr));
              //当temp为0，即lastIndex为0，即第一个元素的索引为最后一次交换的位置时，结束循环
              if (temp == 0){
                  break;
              }
          }
      }
      
      public static void swap(int[] arr, int i, int j) {
          int t = arr[i];
          arr[i] = arr[j];
          arr[j] = t;
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36

• 输出结果：