最近想系统整理一下数据库的索引系列，然后就牵扯到了二分查找，二分查找的前提需要排序。
排序工作中我们用的很多，不过很少去关心实现；面试中，排序的出场率非常高，以此来验证大家是否懂得“算法”。
无论如何，排序算法都值得每一位极客去学习和掌握。
冒泡排序(英语：Bubble Sort)又称为泡式排序，是一种简单的排序算法。
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序对 n 个项目需要 O(n^2) 的比较次数，且可以原地排序。
尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。
冒泡排序算法的运作如下：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。
冒泡排序的文章和实现在网上有很多，讲解的也很详细。
此处只补充一下自己觉得不足的地方：
(1)大部分实现都只是一个 int 比较的例子，实用性不强。
(2)没有统一的接口，不便于后期的统一拓展和自适应。(根据不同的数量，选择不同的算法)
(3)没有自适应性的日志输出，不便于学习。
基于上面 3 点，我们做一点小小的改进。
第一步：统一定义一个排序的接口。
为了便于后期拓展，统一实现一个抽象父类：
这里很简单，针对空列表，或者大小为1的列表，无需进行排序。
接下来我们实现以下冒泡排序即可：
有几点需要说明下：
(1)这里是对 Comparable 对象的支持，本质上和常见的 int 比较一样，这样的适用范围更加广泛一些。
(2)这里是基于 java 的 list 进行排序，因为个人认为 list 的出场率是高于数组的，当然大家如果想实现数组版本的，也是类似的。
(3)changeFlag 也就是我们常说的针对冒泡排序的优化，如果没有变更，说明排序完成，可以直接返回了。
为了让这个实现类使用起来更加方便，我们就模仿一下 jdk 中的方法。提供一个工具类：
我们来验证一下排序算法。
其中 RandomUtil 是一个随机生成的工具，便于我们测试，实现如下：
为了便于理解，我们可以在排序实现中加一点日志：
i,j 代表本次循环的 i,j; c 代表当前值，n 代表 next 下一个值。
测试日志如下：
这个算法，是把小的值放在前面，所以只有当 c > n 的时候，才会发生排序。
最后 i = 6, j = 2 的时候，已经排序完成。
为了便于大家学习，上面的排序已经开源，开源地址：
https://github.com/houbb/sort
欢迎大家 fork/star，鼓励一下作者~~
希望本文对你有帮助，如果有其他想法的话，也可以评论区和大家分享哦。