冒泡排序 — 还有很多你不知道的
本文着重讲解以下几个问题
1、排序算法分类
2、冒泡排序的实现与优化
3、冒泡排序复杂度与稳定性
1、排序算法分类
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
排序算法，就是如何使记录按照要求排列的方法。简单理解就是对一些杂乱无序的数进行排序使其递增或递减。
排序算法在很多领域都相当地重视，尤其在大量数据的处理方面。一个优秀的算法可以节省大量的资源。
在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。
排序算法可分为两大类：内部排序、外部排序
内部排序：就是排序过程只发生在内存中的排序算法
外部排序：由于数据量较大，不能一次性在内存中进行，而要分批次从外部存储读入内存中进行排序后再返回到外部存储的排序算法。
我们平常所说的排序算法，一般都指的是内部排序。
内部排序又可以根据其排序的不同特性，分为以下几类
2、冒泡排序的实现与优化
了解了排序算法的概念和分类之后，下面我们谈论下最基础的冒泡算法是如何实现的。
要了解一个算法，最重要不是记住实现代码，而是了解思想后掌握实现过程。
那么冒泡排序的思想是什么呢？
两个词
比较 交换
牢牢把这两个词刻在冒泡排序上
听起来很简单？
实际上也确实很简单
举例说明：
{12，9，7，5，3，2，1} 这样的一组数，使用冒泡排序递增排序。
第一轮：从第一个元素开始两两比较，前面的大就交换位置。过程是：12与9交换、12与7交换、12与5交换、12与3交换、12与2交换、12与1交换。第一轮结束后的结果为：{9，7，5，3，2，1，12}
同理，第二轮、第三轮依次。每一轮的结果如下
原始：{12，9，7，5，3，2，1}
一轮：{9，7，5，3，2，1，12}
二轮：{7，5，3，2，1，9，12}
三轮：{5，3，2，1，7，9，12}
四轮：{3，2，1，5，7，9，12}
五轮：{2，1，3，5，7，9，12}
六轮：{1，2，3，5，7，9，12}
由此可得出规律：7个数需要排序6轮，每一轮需要比较6次。使用双层for循环即可解决
a>简单优化——优化比较次数
有同学应该已经发现，后面的每一轮排序实际并不都是要比较6次，比较次数是递减的。
第一轮：比较6次
第二轮：比较5次
第三轮：比较4次
第四轮：比较3次
第五轮：比较2次
第六轮：比较1次
这种优化的效果并不是很明显，没有明显的效率提升。
接下来 放大招
b> 进阶优化——优化排序轮数
假设原始数据是这样的{12，7，9，1，2，3，5}
原始：{12，7，9，1，2，3，5}
一轮：{7，9，1，2，3，5，12}
二轮：{7，1，2，3，5，9，12}
三轮：{1，2，3，5，7，9，12}
其实至此我们已经完成了排序，根本不用再进行6轮的排序比较了。
因此我们可以通过设置一个flag变量来监测每一轮排序是否发生了交换。
如果发生了交换证明目前并非已排序状态，还需要继续下一轮排序；
如果没发生交换证明目前是已排序状态，则不需要继续下一轮排序；
这种优化方式的确能够提升排序效率。
但 也仅仅只能当序列中数据部分有序的情况下起作用。那如果数据完全无序，怎么办呢？
接下来 放大大招
3>再进阶优化——双向冒泡排序
听这个名字是不是就感觉到有点高端了。确实也很高端。
从名字来看，双向冒泡排序就是：从两个方向进行排序。
是不是听不懂了？
是这样的！
冒泡排序不是逐次比较嘛。那我可以这样：
从左到右按照递增比较排序， 从右到左按照递减比较排序。
同时进行，每一轮排序后就会有一个最小值和一个最大值被确定出来放在最终位置。
我们只需要每次改变左右两边的范围即可（意思就是已经排序出来的最大值和最小值下一轮就不用比较了）
这样就很霸气了！
3、冒泡排序复杂度与稳定性
最后，我们来说下冒泡算法的复杂度和稳定性。
Let me 先解释一下
时间复杂度：指执行这个算法所需要的计算工作量，可理解为花费时间
空间复杂度：指执行这个算法所需要的内存空间，需要多少额外空间
稳定性：执行这个算法后，原来相同的元素的相对位置是否发生了变化。
例如：
原始：{12，9(1)，9(2)，7，5，3，2，1}
排序后：{1，2，3，5，7，9(1)，9(2)，12} 稳定 因为相对位置未变
排序后：{1，2，3，5，7，9(2)，9(1)，12} 不稳定 因为相对位置变了
直接看图吧！
关注我，快！！！