【数据结构与算法】冒泡排序算法的介绍和程序实现

1. 冒泡排序的介绍

冒泡排序(Bubble Sorting)的基本思想是：通过对待排序序列从前向后(从下标较小的元素开始), 依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒

如果一轮比较下来没有进行过交换，就说明序列有序，不需要进行下一轮的比较了。因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较

算法稳定性：冒泡排序就是把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法

2. 冒泡排序的程序实现

需求：将五个无序的数：3, 9, -1, 10, -2。使用冒泡排序法将其排成一个从小到大的有序数列

步骤

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数
3. 针对所有的元素重复以上的步骤，除了最后一个
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

步骤详解：

第一轮：

1. 9和-1比，9>-1，则它们互换位置：3, -1, 9, 10, -2
2. 10和-2比，10>-2，则它们互换位置：3, -1, 9, -2, 10
3. 此时最大值浮到了最右边

第二轮：

1. 3和-1比，3>-1，则它们互换位置：-1, 3, 9, -2, 10
2. 9和-2比，9>-2，则它们互换位置：-1, 3, -2, 9, 10

第三轮：

1. 3和–2比，3>–2，则它们互换位置：-1, -2, 3, 9, 10

第四轮：

1. -1和–2比，-1>–2，则它们互换位置：-2, -1, 3, 9, 10
2. 至此，排序结束

程序如下：

import java.util.Arrays;

public class BubbleSort {

    public static void main(String[] args) {
        int[] array = {3, 9, -1, 10, -2};

        // 测试冒泡排序
        bubbleSort(array);

        System.out.println("排序后：");
        System.out.println(Arrays.toString(array));
    }

    // 冒泡排序算法实现
    public static void bubbleSort(int[] arr) {
        int tmp = 0;
        // 标识在一轮排序中，是否进行过元素交换
        boolean flag = false;

        // 时间复杂度为O(n^2)
        // 用于控制遍历多少轮
        for (int i = 0; i < arr.length - 1; i++) {
            // 用于控制在一轮中，遍历多少次
            for (int j = 0; j < arr.length - 1 - i; j++) {
                // 如果前面的数比后面的数大，则进行交换。同时flag为true
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }

            // 如果在一轮中没有发生过元素交换，则退出
            if (!flag) {
                break;
            } else {
                // 重置flag，便于下次循环判断
                flag = false;
            }
        }
    }

}

运行程序，结果如下：

排序后：
[-2, -1, 3, 9, 10]