什么是冒泡排序？
摘自漫画算法：
冒泡排序的英文是bubble sort，它是一种基础的交换排序。
大家一定都喝过汽水，汽水中常常有许多小小的气泡哗啦啦飘到上面来。这是因为组成小气泡的二氧化碳比水轻，所以小气泡可以一点一点地向上浮动。
而冒泡排序之所以叫冒泡排序，正是因为这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点地向着数组的一侧移动。
例子：
有8个数字组成一个无序数列{5,8,6,3,9,2,1,7}，希望按照从小到大的顺序对其进行排序。
按照冒泡排序的思想，我们要把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置，当一个元素小于或等于右侧相邻元素时，位置不变。
过程如下：
这样一来，元素9作为数组中最大的元素，就像是汽水里的小气泡一样，“漂”到了最右侧。
这时，冒泡排序的第一轮就结束了。数组最右侧的元素9的位置可以认为是一个有序区域，有序区域目前只有一个元素。
下面，让我们来进行第二轮排序。
过程如下：
第二轮排序结束后，数组右侧的有序区域有了2个元素，顺序如下：
后续的交换细节，就不再详细描述了，第三轮到第七轮的状态如下：
到此为止，所有元素都是有序的了，这就是冒泡排序的整体思路。
冒牌排序是一种稳定排序，值相等的元素并不会打乱原本的顺序。由于该排序算法的每一轮都要遍历所有元素，总共遍历（元素数量 - 1）轮，所以平均时间复杂度是O(n²)。
冒泡排序的实现
整体代码
import java.util.Arrays;
/**
* 描述：冒泡排序
* <p>
* Create By ZhangBiao
* 2020/5/20
*/
public class BubbleSort {
public static void sort(int arr[]) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
int temp = 0;
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
整体代码非常的简单，使用双循环进行排序。外部循环控制所有的回合，内部循环实现每一轮的冒泡处理，先进行元素比较，再进行元素交换。
优化冒泡排序
方式1
原始的冒泡排序有哪些可以优化的点呢？
在刚才描述的排序细节，仍然以{5,8,6,3,9,2,1,7}这个数列为例，当排序算法分别执行到第6轮、第7轮时，数列状态如下：
很明显可以看出，经过第6轮排序后，整个数列已经是有序的了。可以排序算法仍然兢兢业业地继续执行了第7轮排序。
在这种情况下，如果能判断出数列已经有序，并做出标记，那么剩下的几轮排序就不必执行了，可以提前结束工作。
优化后的代码：
import java.util.Arrays;
/**
* 描述：冒泡排序
* <p>
* Create By ZhangBiao
* 2020/5/20
*/
public class BubbleSort {
public static void sort(int arr[]) {
for (int i = 0; i < arr.length - 1; i++) {
//有序标记，每一轮的初始值都是true
boolean isSorted = true;
for (int j = 0; j < arr.length - i - 1; j++) {
int temp = 0;
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
//因为有元素进行交换，所以不是有序的，标记变为false
isSorted = false;
}
}
if (isSorted) {
break;
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
与优化前的代码相比，优化后的代码做了小小的改动，利用布尔变量isSorted作为标记。如果在本轮排序中，有元素交换，则说明数列无序；如果没有元素交换，则说明数列已经是有序的了，然后直接跳出大循环。
方式2
为了说明问题，这次以一个新的数列为例。
这个数列的特点是前半部分的元素（3、4、2、1）无序，后半部分的元素（5、6、7、8）按升序排列，并且后半部分元素中的最小值也大于前半部分元素的最大值。
下面按照冒泡排序的思路来进行排序，看看具体的效果。
第1轮：
元素4和5进行比较，由于4小于5，所以位置不变。
元素5和6进行比较，由于5小于6，所以位置不变。
元素6和7进行比较，由于6小于7，所以位置不变。
元素7和8进行比较，由于7小于8，所以位置不变。
第1轮结束，数列的有序区域包含1个元素。
第2轮：
元素3和2进行比较，由于3大于2，所以元素3与2进行交换。
元素3和1进行比较，由于3大于1，所以元素3与1进行交换。
元素3和4进行比较，由于3小于4，所以位置不变。
元素4和5进行比较，由于4小于5，所以位置不变。
元素5和6进行比较，由于5小于6，所以位置不变。
元素6和7进行比较，由于6小于7，所以位置不变。
元素7和8进行比较，由于7小于8，所以位置不变。
此时第2轮结束，数列有序取悦包含2个元素。
问题：其实右侧的许多元素已经是有序的了，可是每一轮还是白白地浪费时间进行比较。
这个问题的关键点在于对数列有序区域的界定。
按照现在的逻辑，有序区的长度和排序的轮树是相等的。例如第1轮排序过后的有序区域长度是1，第2轮过后有序区域的长度为2 ......。
实际上，数列真正的有序区域可能会大于这个长度，例如上述例子中在第2轮排序时，后面的5个元素实际上都已经属于有序区域了。因此后面的多次元素比较是没有意义的。
那么，如何避免这种情况呢？我们可以在每一轮排序后，记录下来最后一次元素交换的位置，该位置即为无序数列的边界，再往后就是有序区域了。
优化后的代码：
import java.util.Arrays;
/**
* 描述：冒泡排序
* <p>
* Create By ZhangBiao
* 2020/5/20
*/
public class BubbleSort {
public static void sort(int arr[]) {
// 记录最后一次交换的位置
int lastExchangeIndex = 0;
// 无序数列的边界，每次比较只需要比到这里为止
int sortBorder = arr.length - 1;
for (int i = 0; i < arr.length - 1; i++) {
//有序标记，每一轮的初始值都是true
boolean isSorted = true;
for (int j = 0; j < sortBorder; j++) {
int temp = 0;
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
//因为有元素进行交换，所以不是有序的，标记变为false
isSorted = false;
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex;
if (isSorted) {
break;
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
在优化方式2的代码中，sortBorder就是无序数列的边界。在每一轮排序过程中，处于sortBorder之后的元素就不需要再进行比较了，肯定是有序的。
鸡尾酒排序
冒泡排序的每一个元素都可以像小气泡一样，根据自身大小，一点一点地向着数组的一侧移动。算法的每一轮都是从左到右来比较元素，进行单向的位置交换的。
那么鸡尾酒排序做了什么样的优化呢？
鸡尾酒排序的元素比较和交换过程是双向的。
例子：
由8个数字组成一个无需数列{2,3,4,5,6,7,8,1}，希望对其进行从小到大的排序。
如果按照冒泡排序的思路，排序过程如下：
问题：元素2、3、4、5、6、7、8已经是有序的了，只有元素1的位置不对，却还要进行7轮排序！鸡尾酒排序正是要解决这个问题的。
那么鸡尾酒排序是什么样子的呢？过程如下：
第1轮：
此时和冒泡排序一样， 元素8和1进行交换。
第2轮：
此时开始不一样了，我们反过来从右往左比较并进行交换。
第3轮（虽然实际上已经有序了，但是流程并没有结束）：
在鸡尾酒排序的第3轮，需要重新从左向右比较并进行交换。
元素1和2进行比较，由于1小于2，所以位置不变。
元素2和3进行比较，由于2小于3，所以位置不变。
元素3和4进行比较，由于3小于4，所以位置不变。
元素4和5进行比较，由于4小于5，所以位置不练。
元素5和6进行比较，由于5小于6，所以位置不变。
元素6和7进行比较，由于6小于7，所以位置不变。
元素7和8进行比较，由于7小于8，所以位置不变。
此时没有元素进行交换，证明已经有序了，排序结束。
这就是鸡尾酒排序的思路。排序过程就是钟摆一样，第1轮从左到右，第2轮从右到左，第3轮在从左到右，本来需要7轮排序的场景，只用3轮就解决了。
代码如下：
import java.util.Arrays;
/**
* 描述：鸡尾酒排序
* <p>
* Create By ZhangBiao
* 2020/5/20
*/
public class BubbleSort {
public static void sort(int arr[]) {
int temp = 0;
for (int i = 0; i < arr.length / 2; i++) {
// 有序标记，每一轮的初始值都是true
boolean isSorted = true;
// 奇数轮，从左向右比较和交换
for (int j = i; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
// 有元素交换，所以不是有序的，标记变为false
isSorted = false;
}
}
if (isSorted) {
break;
}
// 在偶数轮之前，将isSorted重新标记为true
isSorted = true;
// 偶数轮，从右向左比较和交换
for (int j = arr.length - i - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
// 因为有元素进行交换，所以不是有序的，标记变为false
isSorted = false;
}
}
if (isSorted) {
break;
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{2, 3, 4, 5, 6, 7, 8, 1};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
这段代码是鸡尾酒排序的原始实现。代码外层的大循环控制着所有排序回合，大循环内包含2个小循环，第1个小循环从左向右比较并交换元素，第2个小循环从右向左比较并交换元素。
