[数据结构与算法]冒泡排序算法-java实现

• 最近看了许多算法相关的书籍和博文，就想着自己记录下，大学的时候学习了冒泡排序，现在都快搞忘记了，今天再来回顾下

什么是冒泡排序算法？

• 冒泡排序（Bubble Sort）是一种最基础的交换排序
• 排序思想：相邻元素做比较，决定是否交换位置
• 原始的冒泡排序是稳定排序，时间复杂度是O(N^2)

冒泡排序的java实现

• 原始的冒泡排序java实现，如下

  public class Test {
      public static void main(String[] args) {
          int[] a = {6, 4, 5, 3, 2, 1};
          bubbleSort(a);
          System.out.println("sort:" + Arrays.toString(a));
      }
  
      /**
       * 原始的冒泡升序排序
       *
       * @param array
       */
      public static void bubbleSort(int array[]) {
          int temp;//交换元素的临时变量
          for (int i = 0; i < array.length - 1; i++) {//外层循环遍历的次数array.length - 1
              for (int j = 0; j < array.length - (i + 1); j++) {//内层循环遍历相邻元素进行比较和交换
                  if (array[j] > array[j + 1]) {//相邻的前一个元素大于后一个元素则交换
                      temp = array[j];
                      array[j] = array[j + 1];
                      array[j + 1] = temp;
                  }
              }
          }
      }
  }
  

冒泡排序的优化

• 原始的冒泡排序实现很简单，比较稳定，时间复杂度基本不变
• 如果是一个有序的数组进行排序，也是需要同样多的时间
• 排序的中途已经有序了，那么我们就没必要在进行循环遍历了
• 如果我们遍历一遍后没有交换元素则直接跳出循环，排序完成
• 如果在循环遍历相邻元素的过程中，有部分数组已经有序了，那么我们则没有必要在遍历后面的元素了
• 我们在遍历的过程中，记录下最后一次交换元素时的下标(这个下标就是有序区和无序区的边界)，下次循环的边界则是这个上次最后一次交换元素的下标
• 优化后的冒泡排序java实现，如下：

  public class Test {
      public static void main(String[] args) {
          int[] a = {2, 11, 10, 3, 9, 2, 6, 4, 5, 3, 2, 1};
          bubbleSort(a);
          System.out.println("sort:" + Arrays.toString(a));
      }
  
      /**
       * 优化后的冒泡升序排序
       *
       * @param array
       */
      public static void bubbleSort(int array[]) {
          int temp;//交换元素的临时变量
          int boundary = array.length - 1;//无序区的边界，每次比较元素到这里
          for (int i = 0; i < array.length - 1; i++) {//外层循环遍历的次数array.length - 1
              boolean sorted = true;//有序标记，每一轮都设置为true
              int lastExchange = 0;//最后一次交换元素的位置
              for (int j = 0; j < boundary; j++) {//内层循环遍历相邻元素进行比较和交换
                  if (array[j] > array[j + 1]) {//相邻的前一个元素大于后一个元素则交换
                      temp = array[j];
                      array[j] = array[j + 1];
                      array[j + 1] = temp;
                      sorted = false;//有元素交换，设置排序完成为false
                      lastExchange = j;//有元素交换，记录下交换的下标
                  }
              }
  
              boundary = lastExchange;//最后一次交换元素的下标就是下次遍历的边界
              if (sorted) {//排序完成
                  break;
              }
          }
      }
  }