面试必备：经典算法动画解析之冒泡排序

哈喽，我是程序员大鹏。

最近在招聘过程中，发现好多小伙伴最基础的一些算法回答，接下来会做一个系列，把基础的排序等算法采用动画的形式做解析。

这是第一篇冒泡排序。

冒泡排序思想

冒泡排序(Bubble Sort)是一种交换排序，基本思想是两两比较相邻记录，如果逆序则进行交换，直到没有逆序的记录为止。

冒泡算法有很多种实现方式，我们在这里只列举出来两种实现方式来讲解冒泡排序。

排序原理

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

排序动画

排序实现

简单的冒泡排序

  public static void sort(int[] arg) {
    //冒泡排序
    for (int i = 0; i < arg.length - 1; i++) {
      for (int j = arg.length - 1; j > i; j--) {
        if (arg[j] < arg[j - 1]) {//交换两个数字
          int temp = arg[j];
          arg[j] = arg[j - 1];
          arg[j - 1] = temp;
        }
      }
    }
  }

上面的代码是根据动画进行的实现，假设我们的数据为{7,5,1,3,2,6}，当i=0时，进行第一轮排序，变量j由5开始一直循环到1，逐个进行两两相邻数字的比较，最后将数字最小的1排到第一位，当i=1时，进行第二轮排序，变量j由5开始一直循环到2，逐个进行两两相邻数字的比较，最后将数字2排到第二位，依次进行i的下一轮比较，最终实现了数据的排序。

在这个过程中，由于数字像是浮起来的泡泡，所以称之为冒泡排序。

排序优化

上面的算法还有优化的空间吗？我们来看下面的这组数据，比如{6,5,4,3,1,2}，经过一轮排序已经变为了{6,5,4,3,2,1}，第二轮开始排序之后，还是{6,5,4,3,2,1}，数字的顺序是没有改变的，说明数字已经处于排序的状态了，则没有必要进行排序，所以还可以进行优化，代码如下：

  public void sort(int[] arg) {
    //冒泡排序优化
    for (int i = 0; i < arg.length - 1; i++) {
      boolean isSorted = true;
      for (int j = arg.length - 1; j > i; j--) {
        if (arg[j] < arg[j - 1]) {//交换两个数字
          int temp = arg[j];
          arg[j] = arg[j - 1];
          arg[j - 1] = temp;
          isSorted = false;//如果有数据交换，则isSorted为false
        }
      }
      if (isSorted) {//isSorted为true，说明没有进行数据交换，数据已经有序，则退出循环
        break;
      }
    }
  }

这样经过上面的优化，冒泡排序会避免在数据已经有序的情况下继续进行数据循环比较，性能得到了一定的提升。

冒泡排序的复杂度分析

数据正序的情况

比如数据为{6,5,4,3,2,1}，按照优化后的算法，只需要，只会进行5次比较，也就是n-1次的比较，所以时间复杂度为O{n}

数据逆序的情况

最坏的情况就是全部数据都是逆序，比如{6,5,4,3,2,1}，(n(n-1))/2次的数据操作和数据移动，所以总的时间复杂度为 (O(n2))

综合上面的情况，冒泡排序的时间复杂度为(O(n2))

Tags: JAVA 数据结构与算法算法经典排序