相信很多学习计算机的同学接触的第一个算法就是冒泡排序，如果现在让你手写冒泡排序算法，你还记得吗？
冒泡排序是一种简单直观的排序算法，也是一种最基础的交换排序。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
冒泡排序算法的原理如下：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
如果文字讲得过于晦涩，可以来看看这张图：
从序列的一端开始往另一端冒泡（你可以从左往右冒泡，也可以从右往左冒泡，看心情），依次比较相邻的两个数的大小（到底是比大还是比小也看你心情）。
当然，如果你习惯从左往右冒泡的话，可以看这张图：
维基百科上对冒泡排序的动画展示如下：
我们拆解一步步来看，以 [ 8，2，5，9，7 ] 这组数字来做示例，从左往右依次冒泡，将小的往右移动。
第一轮冒泡如下：
指针再往右移动，发现已经到底了，则本轮冒泡结束，处于最右边的 2 就是已经排好序的数字。通过这一轮不断的对比交换，数组中最小的数字移动到了最右边。
第二轮冒泡如下：
由于右边的 2 已经是排好序的数字，就不再参与比较，所以本轮冒泡结束，本轮冒泡最终冒到顶部的数字 5 也归于有序序列中：
第三轮冒泡如下：
由于 8 比 7 大，所以位置不变，此时第三轮冒泡也已经结束。
第四轮冒泡如下：
9 和 8 比，位置不变，即确定了 8 进入有序序列，那么最后只剩下一个数字 9 ，放在末尾，至此排序结束。
代码如下：
public static void bubbleSort(int[] arr) {
int temp;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] < arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
代码非常简单，使用双循环来进行排序。外部循环控制冒泡轮数，内部循环代表每一轮的冒泡处理，先进行元素比较，再进行元素交换。
接下来再看看能否对代码进行性能优化。
引入一个新数组并从小到大排序：
经过六轮排序后数组如下：
第七轮：
第八轮：
很明显可以看出，自从经过第六轮排序，整个数列已然是有序的了。可是我们的排序算法仍然兢兢业业地继续执行第七轮和第八轮。
这种情况下，如果我们能判断出数列已经有序，并且做出标记，剩下的几轮排序就可以不必执行，提早结束工作。
优化后代码如下：
public static void bubbleSort(int[] arr) {
int temp;
for (int i = 0; i < arr.length - 1; i++) {
boolean isSorted = true;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSorted = false;
}
}
if (isSorted) {
break;
}
}
}
利用布尔变量作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，说明数列已然有序，直接跳出大循环。
很多博客基本都是优化至此就结束了，其实还可以继续优化。
再引入一个新数组：
可以看到该数组后半部分已升序且为数列最大值。因此前四轮冒泡确定的有序数列实际上在未排序前就已经是有序的，而上述算法每一轮都要作一些无用功，这就是需要优化的地方。
这个问题的关键点在于对数列有序区的界定。
按照现有的逻辑，有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是 1，第二轮排序过后的有序区长度是 2……
实际上，数列真正的有序区可能会大于这个长度，比如例子中仅仅第二轮，后面 6 个元素实际都已经属于有序区。因此后面的许多次元素比较是没有意义的。
如何避免？我们可以在每一轮排序的最后，记录下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了。
优化后代码如下：
public static void bubbleSort(int[] arr) {
int temp;
int lastExchangeIndex = 0; // 记录最后一次交换的位置
int sortBorder = arr.length - 1; // 无序数列的边界，每次比较只需要比到这里为止
for (int i = 0; i < arr.length - 1; i++) {
boolean isSorted = true; // 有序标记，每一轮的初始是 true
for (int j = 0; j < sortBorder; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSorted = false; // 有元素交换，所以不是有序，标记变为 false
lastExchangeIndex = j; // 把无序数列的边界更新为最后一次交换元素的位置
}
}
sortBorder = lastExchangeIndex;
if (isSorted) {
break;
}
}
}
这里引入了一个新的变量用来记录无需数组的边界，每一轮排序过程中，边界之后的元素就完全不需要比较了，因为它们肯定是有序的。
冒泡排序是把小的元素往前调或者把大的元素往后调，比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
算法中有两重嵌套循环，所以容易得出，冒泡排序算法的时间复杂度为 O(n²)。