回顾一下排序算法，老酒装新瓶，给自己的技能点做个回放。
排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素(或记录)的任意序列，重新排列成一个有序的序列，也可以理解为高矮个站队。
衡量排序算法的两个指标，时间复杂度 和 稳定性。
举个例子，如果我们的数据是：3 5 4 2 2, 稳定的排序最后的俩个2在排好序后他们的原始前后顺序是不会变的(第一个2还在第二个2的前面，有点绕，你可以理解为小明和小强一样高，最开始小明在小强的前面，排完序之后，小明还在小强前面，就属于稳定的排序），不稳定的排序最后两个2的顺序可能交换（也就是可能小明在前，也可能小强在前）。
时间复杂度先跳过哈，我回头单独写一篇文章介绍，本文主要介绍和实操“冒泡排序”。
介绍
冒泡排序是將比較大的數字移到序列的后面，较小的移到前面。
从第一个开始，第一个和第二个比，谁高（大）谁站后面（两个人（数）的位置交换，不是最后面），当前第二个再与第三个比，依次进行，一轮下来之后，筛选出来最高个（大）的人（数）。
上面就表示第一轮结束了，第二轮和第一轮一样，只是最后一个人（数）已经排好了，不用管他了。
经过 N-1 轮之后，排序完成。
N 个人，经过 N-1 轮，相当于 N*(N-1)=N^2-N, 时间复杂度取最大的 O(n^2)
实例
原始数据：
3 5 2 6 2
第一轮
比较 3 和 5，5 大于 3 ，不需交换
3 5 2 6 2
继续比较 5 和 2，5 大于 2，交换位置
3 2 5 6 2
继续比较 5 和 6，6 大于 5，不需交换
3 2 5 6 2
继续比较 6 和 2，6 大于 2，交换位置
3 2 5 2 6
6 移到最后，两个2都分别向前移动。
第二轮
比较 3 和 2， 3 大于 2，交换位置
2 3 5 2 6
比较 3 和 5， 5 大于 3，不需交换
2 3 5 2 6
比较 5 和 2， 5 大于 2，交换位置
2 3 2 5 6
不需比较 5 和 6
第三轮
比较 2 和 3， 3 大于 2，不需交换
2 3 2 5 6
比较 3 和 2， 3 大于 2，交换位置
2 2 3 5 6
不需比较了
第四轮
比较 2 和 2，不需交换
2 2 3 5 6
四轮结束，最终的结果：
2 2 3 5 6
Java 实现
public class Bubble {
/**
* 冒泡排序
*/
public static int[] sort(int[] array) {
int temp;
// 第一层循环表明比较的轮数, 比如 length 个元素,比较轮数为 length-1 次（不需和自己比）
for (int i = 0; i < array.length - 1; i++) {
System.out.println("第" + (i + 1) + "轮开始");
// 第二层循环，每相邻的两个比较一次，次数随着轮数的增加不断减少，每轮确定一个最大的，不需比较那个最大的
for (int j = 0; j < array.length - 1 - i; j++) {
System.out.println("第" + (i + 1) + "轮，第" + (j + 1) + "次比较：");
if (array[j + 1] < array[j]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
for (int k : array) {
System.out.print(k + " ");
}
System.out.println();
}
System.out.println("结果：");
for (int k : array) {
System.out.print(k + " ");
}
System.out.println();
}
return array;
}
public static void main(String[] args) {
int[] array = {3, 5, 2, 6, 2};
int[] sorted = sort(array);
System.out.println("最终结果");
for (int i : sorted) {
System.out.print(i + " ");
}
}
}
输出结果：
第1轮开始
第1轮，第1次比较：
3 5 2 6 2
第1轮，第2次比较：
3 2 5 6 2
第1轮，第3次比较：
3 2 5 6 2
第1轮，第4次比较：
3 2 5 2 6
结果：
3 2 5 2 6
第2轮开始
第2轮，第1次比较：
2 3 5 2 6
第2轮，第2次比较：
2 3 5 2 6
第2轮，第3次比较：
2 3 2 5 6
结果：
2 3 2 5 6
第3轮开始
第3轮，第1次比较：
2 3 2 5 6
第3轮，第2次比较：
2 2 3 5 6
结果：
2 2 3 5 6
第4轮开始
第4轮，第1次比较：
2 2 3 5 6
结果：
2 2 3 5 6
最终结果
2 2 3 5 6
优化改进
对冒泡排序常见的改进方法是加入一标志性变量 pos ，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换（都不需要交换，肯定排好了），则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。
设置一标志性变量 pos,用于记录每趟排序中最后一次进行交换的位置（后面有多个没有发生交换，说明后面已经排好了）。由于 pos 位置之后的记录均已交换到位，故在进行下一趟排序时只要排到 pos 位置即可。
怎么理解呢？
以 3 2 4 5 6 为例
第一轮排序，发生交换的位置仅仅是 3 和 2， 则 pos 是 0（索引位置从0开始）
直接一轮就结束了，而不用傻傻的再跑4轮。
代码实现：
public class Bubble {
/**
* 冒泡排序（优化改进版）
*/
public static int[] sort(int[] array) {
int temp;
int time = 1;
for (int i = array.length - 1; i > 0; ) {
System.out.println("第" + time + "轮开始");
int pos = 0;
// 第二层循环，每相邻的两个比较一次，次数随着轮数的增加不断减少，每轮确定一个最大的，不需比较那个最大的
for (int j = 0; j < i; j++) {
System.out.println("第" + time + "轮，第" + (j + 1) + "次比较：");
if (array[j + 1] < array[j]) {
// 记录最后一次交换位置的索引，下一轮只需排序到 pos 位置
pos = j;
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
for (int k : array) {
System.out.print(k + " ");
}
System.out.println();
}
// 之前是 i--, 优化后直接跳到最后交换位置的索引
i = pos;
time++;
System.out.println("结果：");
for (int k : array) {
System.out.print(k + " ");
}
System.out.println();
}
return array;
}
public static void main(String[] args) {
int[] array = {3, 2, 4, 5, 6};
int[] sorted = sort(array);
System.out.println("最终结果");
for (int i : sorted) {
System.out.print(i + " ");
}
}
}
结果输出：
第1轮开始
第1轮，第1次比较：
2 3 4 5 6
第1轮，第2次比较：
2 3 4 5 6
第1轮，第3次比较：
2 3 4 5 6
第1轮，第4次比较：
2 3 4 5 6
结果：
2 3 4 5 6
最终结果
2 3 4 5 6
本次的分享到此结束，希望对你有所帮助。
如果你对我分享的内容感兴趣，欢迎扫码关注公众号：新质程序猿，并设置星标，推送更实时哟！
