动画解析冒泡排序
最近在招聘过程中，发现好多小伙伴最基础的一些算法回答，接下来会做一个系列，把基础的排序等算法采用动画的形式做解析。
这是第一篇「冒泡排序」。
冒泡排序思想
冒泡排序(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))」
