冒泡排序

1. 前言

本节内容是排序算法系列之一：冒泡排序，主要讲解了冒泡排序的主体思路，选取了一个待排序的数字列表对冒泡排序算法进行了演示，给出了冒泡排序算法的 Java 代码实现，帮助大家可以更好地理解冒泡排序算法。

2. 什么是冒泡排序？

冒泡排序（Bubble Sort），是计算机科学与技术领域中较为简单的一种排序算法。

它重复地遍历要排序的序列，会依次比较两个相邻的元素，如果发现两个相邻的元素顺序错误就把它们交换过来。遍历序列的工作会重复地进行直到没有相邻的元素需要交换位置，也就是说序列的排序工作已经完成。

冒泡排序的算法名称的由来就是因为在排序的过程中，按照排序规则（升序或者降序），越小或者越大的元素会经过交换之后慢慢 “浮” 到序列的顶端，就如同水中的气泡一样最终会浮到顶端一样，所以起名为 “冒泡排序”。

3. 冒泡排序过程

在介绍完冒泡排序之后，我们一起来看一下冒泡排序的实现步骤具体是什么样的吧。这里我们假设待排序的序列为 [9,2,11,7,12,5]，我们按照从小到大的序列进行排序。

3.1 算法步骤

1. 步骤 1：

比较待排序序列中相邻的两个元素，如果发现左边的元素比右边的元素大，则交换这两个元素；

2. 步骤 2：

每一对相邻的两个元素重复步骤 1 的动作，从左至右依次执行；

3. 步骤 3：

针对待排序序列中除了最右边的一个元素之外，重复步骤 1， 步骤 2 的工作；

4. 步骤 4：

持续以上步骤 1， 步骤 2， 步骤 3 的工作，每重复一次需要排序的序列中少一个最右边的元素，直到没有任何一对数字需要比较排序。

其实，上面的步骤 2 每执行一次，都有一个排序好的数字放到需要排序的序列的最右边，这样一直重复，可以完成最开始的整个待排序序列的排序工作。接下来，让我们用上面的待排序数字队列 [9,2,11,7,12,5] 进行整个算法步骤的排序演示工作。

3.2 算法演示

按照排序步骤，首先我们会比较待排序序列中（9,2）这一对需要排序的序列，按照从小到大进行排序，需要交换位置，形成序列（2,9），如下：

接着，我们调用步骤 2，重复每一对的排序工作，整个过程如下：

步骤 2 会依次比较待排序序列中相邻的两个元素，按照如上过程一样。当相邻的两个元素已经是排序好的时候，无需交换顺序，否则交换相邻两个元素的顺序。

Tips: 步骤 2 每执行一次都会有一个元素排序好，就是所谓的冒泡的过程，按照从小到大的顺序排列时，每次都会有一个最大的元素排序好，放在待排序序列的最右边。

完成步骤 2 之后，说明我们已经把最大的一个元素 12 排序好啦，接下来我们只需要对序列 [2,9,7,11,5] 进行排序即可，就如 步骤 3 描述一下，然后重复 步骤 1， 步骤 2 中的工作，具体过程执行如下：

我们发现当我们执行 步骤 3 之后，之前的待排序队列 [2,9,7,11,5] 中的最大的一个元素 11 又已经排序好啦，接下来我们只需要调用 步骤 4 的工作，重复之前 步骤 1， 步骤 2， 步骤 3，这里我们就不在演示，只是重复性的进行排序工作，每执行一次 步骤 4，就已经把一个元素排序好，待排序的序列中就减少了一个序列，每次会有一个排序好的数字和一个剩下的待排序数列。其实，整个过程如下：

从上面的示例可以看出，其实整个冒泡排序的过程，每次都会把最大的一个数字排序出来，放在整个序列的最右边，重复执行整个过程，直到整个序列中已经没有需要排序的数值了。

4. Java 代码实现

在说明冒泡排序的整个过程之后，接下来，我们看看如何用 Java 代码实现冒泡排序算法。

import java.util.Arrays;

public class BubbleSort {

    public static void main(String[] args) {
        
        //初始化需要排序的数组
        int array[] = {9,2,11,7,12,5};
        
        //对需要排序的数组进行排序
        for (int i=1; i<array.length; i++){
            
            //针对待排序序列中除了已经排序好的元素之外，重复排序工作
            for(int j=0;j<array.length-i;j++){
                
                //当相邻两个元素需要交换时，交换相邻的两个元素
                if(array[j]>array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
        //打印出排序好的序列
        System.out.println(Arrays.toString(array));
    }

}

运行结果如下：

[2, 5, 7, 9, 11, 12]

代码中的第 8 行初始化一个需要排序的数组，后面按照从小到大的排序规则，实现了数组的排序。第 11 行是外层循环，不断地重复排序工作。第 14 行是内层循环，不断地实现每一次 “冒泡” ，将最大的一个元素找出。第 17 至第 21 行实现当相邻两个元素需要交换时，交换相邻的两个元素的功能。第 25 行打印出排序好的数组。

5. 小结

本节主要学习了冒泡排序算法，在学完本节课程之后，需要熟悉冒泡排序的算法流程，知道冒泡排序算法的实现思路，可以自己用代码实现冒泡排序算法。