4.2.1 初识冒泡排序
什么是冒泡排序？
冒泡排序的英文是bubble sort ，它是一种基础的交换排序 。
大家一定都喝过汽水，汽水中常常有许多小小的气泡哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水轻，所以小气泡可以一点一点地向上浮动。
而冒泡排序之所以叫冒泡排序，正是因为这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点地向着数组的一侧移动。
具体如何移动呢？让我们先来看一个例子。
有8个数字组成一个无序数列{5,8,6,3,9,2,1,7}，希望按照从小到大的顺序对其进行排序。
按照冒泡排序的思想，我们要把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变 。详细过程如下。
这样一来，元素9作为数列中最大的元素，就像是汽水里的小气泡一样，“漂”到了最右侧。
这时，冒泡排序的第1轮就结束了。数列最右侧元素9的位置可以认为是一个有序区域，有序区域目前只有1个元素。
下面，让我们来进行第2轮排序。
第2轮排序结束后，数列右侧的有序区有了2个元素，顺序如下。
后续的交换细节，这里就不详细描述了，第3轮到第7轮的状态如下。
到此为止，所有元素都是有序的了，这就是冒泡排序的整体思路。
冒泡排序是一种稳定排序 ，值相等的元素并不会打乱原本的顺序。由于该排序算法的每一轮都要遍历所有元素，总共遍历（元素数量-1 ）轮，所以平均时间复杂度是O(n 2 ) 。
OK，冒泡排序的思路我大概明白了，那么，怎么用代码来实现呢？
原始的冒泡排序代码我写了一下，你来看一看。
冒泡排序第1版 代码示例如下：
1. public static void sort(int array[])
2. {
3. for(int i = 0; i < array.length - 1; i++)
4. {
5. for(int j = 0; j < array.length - i - 1; j++)
6. {
7. int tmp = 0;
8. if(array[j] > array[j+1])
9. {
10. tmp = array[j];
11. array[j] = array[j+1];
12. array[j+1] = tmp;
13. }
14. }
15. }
16. }
17.
18. public static void main(String[] args){
19. int[] array = new int[]{5,8,6,3,9,2,1,7};
20. sort(array);
21. System.out.println(Arrays.toString(array));
22. }
代码非常简单，使用双循环进行排序。外部循环控制所有的回合，内部循环实现每一轮的冒泡处理，先进行元素比较，再进行元素交换。
原来如此，冒泡排序的代码并不难理解呢。
这只是冒泡排序的原始实现，还存在很大的优化空间呢。
4.2.2 冒泡排序的优化
原始的冒泡排序有哪些可以优化的点呢？
让我们回顾一下刚才描述的排序细节，仍然以{5,8,6,3,9,2,1,7}这个数列为例，当排序算法分别执行到第6、第7轮时，数列状态如下。
很明显可以看出，经过第6轮排序后，整个数列已然是有序的了。可是排序算法仍然兢兢业业地继续执行了第7轮排序。
在这种情况下，如果能判断出数列已经有序，并做出标记，那么剩下的几轮排序就不必执行了，可以提前结束工作。
冒泡排序第2版 代码示例如下：
1. public static void sort(int array[])
2. {
3. for(int i = 0; i < array.length - 1; i++)
4. {
5. //有序标记，每一轮的初始值都是true
6. boolean isSorted = true;
7. for(int j = 0; j < array.length - i - 1; j++)
8. {
9. int tmp = 0;
10. if(array[j] > array[j+1])
11. {
12. tmp = array[j];
13. array[j] = array[j+1];
14. array[j+1] = tmp;
15. //因为有元素进行交换，所以不是有序的，标记变为false
16. isSorted = false;
17. }
18. }
19. if(isSorted){
20. break;
21. }
22. }
23. }
24.
25. public static void main(String[] args){
26. int[] array = new int[]{5,8,6,3,9,2,1,7};
27. sort(array);
28. System.out.println(Arrays.toString(array));
29. }
与第1版代码相比，第2版代码做了小小的改动，利用布尔变量isSorted作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，则说明数列已然有序，然后直接跳出大循环。
不错呀，原来冒泡排序还可以这样优化。
这只是冒泡排序优化的第一步，我们还可以进一步来提升它的性能。
为了说明问题，这次以一个新的数列为例。
这个数列的特点是前半部分的元素（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和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个元素实际上都已经属于有序区了。因此后面的多次元素比较是没有意义的。
那么，该如何避免这种情况呢？我们可以在每一轮排序后，记录下来最后一次元素交换的位置，该位置即为无序数列的边界，再往后就是有序区了。
冒泡排序第3版 代码示例如下：
1. public static void sort(int array[])
2. {
3. //记录最后一次交换的位置
4. int lastExchangeIndex = 0;
5. //无序数列的边界，每次比较只需要比到这里为止
6. int sortBorder = array.length - 1;
7. for(int i = 0; i < array.length - 1; i++)
8. {
9. //有序标记，每一轮的初始值都是true
10. boolean isSorted = true;
11. for(int j = 0; j < sortBorder; j++)
12. {
13. int tmp = 0;
14. if(array[j] > array[j+1])
15. {
16. tmp = array[j];
17. array[j] = array[j+1];
18. array[j+1] = tmp;
19. // 因为有元素进行交换，所以不是有序的，标记变为false
20. isSorted = false;
21. // 更新为最后一次交换元素的位置
22. lastExchangeIndex = j;
23. }
25. sortBorder = lastExchangeIndex;
26. if(isSorted){
27. break;
28. }
29. }
30. }
31.
32. public static void main(String[] args){
33. int[] array = new int[]{3,4,2,1,5,6,7,8};
34. sort(array);
35. System.out.println(Arrays.toString(array));
36. }
在第3版代码中，sortBorder就是无序数列的边界。在每一轮排序过程中，处于sortBorder之后的元素就不需要再进行比较了，肯定是有序的。
真是学到了很多知识，想不到冒泡排序可以玩出这么多花样！
其实这仍然不是最优的，还有一种排序算法叫作鸡尾酒排序 ，是基于冒泡排序的一种升级排序法。
4.2.3 鸡尾酒排序
冒泡排序的每一个元素都可以像小气泡一样，根据自身大小，一点一点地向着数组的一侧移动。算法的每一轮都是从左到右来比较元素，进行单向的位置交换的 。
那么鸡尾酒排序做了怎样的优化呢？
鸡尾酒排序的元素比较和交换过程是双向 的。
下面举一个例子。
由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比较，位置不变；2和3比较，位置不变；3和4比较，位置不变……6和7比较，位置不变。
没有元素位置进行交换，证明已经有序，排序结束。
这就是鸡尾酒排序的思路。排序过程就像钟摆一样，第1轮从左到右，第2轮从右到左，第3轮再从左到右……
哇，本来要用7轮排序的场景，用3轮就解决了，鸡尾酒排序可真是巧妙的算法！
确实挺巧妙的，让我们来看一下它的代码实现吧。
1. public static void sort(int array[])
2. {
3. int tmp = 0;
4. for(int i=0; i
5. {
6. //有序标记，每一轮的初始值都是true
7. boolean isSorted = true;
8. //奇数轮，从左向右比较和交换
9. for(int j=i; j
10. {
11. if(array[j] > array[j+1])
12. {
13. tmp = array[j];
14. array[j] = array[j+1];
15. array[j+1] = tmp;
16. // 有元素交换，所以不是有序的，标记变为false
17. isSorted = false;
18. }
19. }
20. if(isSorted){
21. break;
22. }
// 在偶数轮之前，将isSorted重新标记为true
23. isSorted = true;
24. //偶数轮，从右向左比较和交换
25. for(int j=array.length-i-1; j>i; j--)
26. {
27. if(array[j] < array[j-1])
28. {
29. tmp = array[j];
30. array[j] = array[j-1];
31. array[j-1] = tmp;
33. isSorted = false;
34. }
35. }
36. if(isSorted){
37. break;
38. }
39. }
40. }
41.
42. public static void main(String[] args){
43. int[] array = new int[]{2,3,4,5,6,7,8,1};
44. sort(array);
45. System.out.println(Arrays.toString(array));
46. }
这段代码是鸡尾酒排序的原始实现。代码外层的大循环控制着所有排序回合，大循环内包含2个小循环，第1个小循环从左向右比较并交换元素，第2个小循环从右向左比较并交换元素。
代码大致看明白了。之前讲冒泡排序时，有一种针对有序区的优化，鸡尾酒排序是不是也能用到呢？
当然喽！鸡尾酒排序也可以和之前所学的优化方法结合使用，只不过代码实现会稍微复杂一些，这里就不再展开讲解了，有兴趣的话，可以自己写一下代码实现哦。
OK，最后我想问问，鸡尾酒排序的优点和缺点是什么？适用于什么样的场景？
鸡尾酒排序的优点是能够在特定条件下，减少排序的回合数；而缺点也很明显，就是代码量几乎增加了1倍。
至于它能发挥出优势的场景，是大部分元素已经有序 的情况。好了，关于冒泡排序和鸡尾酒排序，我们就介绍到这里喽。下一节再见！