创作目的最近想系统整理一下数据库的索引系列 ， 然后就牵扯到了二分查找 ， 二分查找的前提需要排序 。
排序工作中我们用的很多 ， 不过很少去关心实现；面试中 ， 排序的出场率非常高 ， 以此来验证大家是否懂得“算法” 。
无论如何 ， 排序算法都值得每一位极客去学习和掌握 。
文章插图
冒泡排序冒泡排序（英语：Bubble Sort）又称为泡式排序 ， 是一种简单的排序算法 。
它重复地走访过要排序的数列 ， 一次比较两个元素 ， 如果他们的顺序错误就把他们交换过来 。 走访数列的工作是重复地进行直到没有再需要交换 ， 也就是说该数列已经排序完成 。 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端 。
冒泡排序对 n 个项目需要 O(n^2) 的比较次数 ， 且可以原地排序 。
尽管这个算法是最简单了解和实现的排序算法之一 ， 但它对于包含大量的元素的数列排序是很没有效率的 。
流程冒泡排序算法的运作如下：

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

由于它的简洁 ， 冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念 。
文章插图
代码实现已有实现的不足冒泡排序的文章和实现在网上有很多 ， 讲解的也很详细 。
此处只补充一下自己觉得不足的地方：
（1）大部分实现都只是一个 int 比较的例子 ， 实用性不强 。
（2）没有统一的接口 ， 不便于后期的统一拓展和自适应 。 （根据不同的数量 ， 选择不同的算法）
（3）没有自适应性的日志输出 ， 不便于学习 。
接口定义基于上面 3 点 ， 我们做一点小小的改进 。
第一步：统一定义一个排序的接口 。
package com.github.houbb.sort.api;import java.util.List;/** * 排序接口 * @author binbin.hou * @since 0.0.1 */public interface ISort {/*** 排序* @param original 原始列表* @since 0.0.1*/void sort(List original);}抽象实现为了便于后期拓展 ， 统一实现一个抽象父类：
package com.github.houbb.sort.core.api;import com.github.houbb.heaven.util.util.CollectionUtil;import com.github.houbb.sort.api.ISort;import java.util.List;/** * 抽象排序实现 * @author binbin.hou * @since 0.0.1 */public abstract class AbstractSort implements ISort {@Overridepublic void sort(List original) {//fail-returnif(CollectionUtil.isEmpty(original) || original.size() == 1) {return;}doSort(original);}/*** 执行排序* @param original 原始结果* @since 0.0.1*/protected abstract void doSort(List original);}这里很简单 ， 针对空列表 ， 或者大小为1的列表 ， 无需进行排序 。
文章插图
冒泡排序接下来我们实现以下冒泡排序即可：
有几点需要说明下：
（1）这里是对 Comparable 对象的支持 ， 本质上和常见的 int 比较一样 ， 这样的适用范围更加广泛一些 。
（2）这里是基于 java 的 list 进行排序 ， 因为个人认为 list 的出场率是高于数组的 ， 当然大家如果想实现数组版本的 ， 也是类似的 。
（3）changeFlag 也就是我们常说的针对冒泡排序的优化 ， 如果没有变更 ， 说明排序完成 ， 可以直接返回了 。
package com.github.houbb.sort.core.api;import com.github.houbb.heaven.annotation.ThreadSafe;import com.github.houbb.log.integration.core.Log;import com.github.houbb.log.integration.core.LogFactory;import java.util.List;/** * 冒泡排序 * @author binbin.hou * @since 0.0.1 */@ThreadSafepublic class BubbleSort extends AbstractSort {private static final Log log = LogFactory.getLog(BubbleSort.class);@Override@SuppressWarnings("unchecked")public void doSort(List original) {boolean changeFlag;for(int i = 0; i < original.size()-1; i++) {changeFlag = false;for(int j = 0; j < original.size()-1-i; j++) {// 如果 j > j+1Comparable current = (Comparable) original.get(j);Comparable next = (Comparable) original.get(j+1);if(current.compareTo(next) > 0) {swap(original, j, j+1);changeFlag = true;}}// 如果没发生置换 ， 说明后面已经排序完成if(!changeFlag) {return;}}}/*** 执行数据的交换* @param original 原始* @param i 第一个* @param j 第二个* @since 0.0.1*/@SuppressWarnings("unchecked")private void swap(List original,int i, int j) {Object temp = original.get(i);original.set(i, original.get(j));original.set(j, temp);}}

• 上一页
• 1
• 2
• 下一页

• 三年Java开发，刚从美团、京东、阿里面试归来，分享个人面经
• java面试题整理
• 面试官：问你一个，Spring事务是如何传播的？
• 程序员面试主要看哪些 该怎么准备面试内容
• 震惊！京东T4大佬面试整整三个月，才写了两份java面试笔记
• 2020金九银十安卓面试题来袭(猿辅导+斗鱼+字节+腾讯)
• 「8」进大厂必须掌握的面试题-Java面试-异常和线程
• 安卓面试必备的JVM虚拟机制详解，看完之后简历上多一个技能
• 成功拿下阿里P6的offer后，总结出大厂面试的血泪史
• 面试官：聊聊 etcd 中的 Raft 吧