动画解析冒泡排序 _冒泡排序

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

文章插图

冒泡排序思想冒泡排序(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;      }    }  }

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