看动图学算法：冒泡排序算法的原理和Java讲解

冒泡算法是一种简单的排序算法，它的基本思想是通过相邻元素之间的比较和交换，将大的元素慢慢地“冒泡”到数组的最后一个位置。冒泡算法在实现上非常简单，但它的时间复杂度较高，通常仅适用于小型数据集的排序。

一、算法原理

冒泡算法的原理非常简单：首先将要排序的数列分成两部分，已排序的部分和未排序的部分。每一轮排序中，从第一个元素开始，依次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换两个元素的位置，直到整个数列都排好序为止。

假设要排序的数列为A[]，其长度为n。则第一轮排序时需要比较n-1次，第二轮排序时需要比较n-2次，以此类推，第k轮排序时需要比较n-k次。因此，总共需要进行n(n-1)/2次比较，时间复杂度为O(n^2)。

二、算法流程

具体来说，冒泡算法的流程如下：

1、首先，将要排序的数列A[]作为输入，其长度为n；

2、然后，从第一个元素开始，依次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换两个元素的位置；

3、接着，将指针向后移动一位，继续比较相邻的两个元素，并进行交换，直到整个数列都排好序为止；

4、最后，输出已排序的数列A[]。

三、优化算法

冒泡排序的时间复杂度为O(n^2)，当数据量较大时，会出现比较耗费时间的情况。因此，我们可以进行一些优化，使得算法的效率更高。

1、当在某一轮排序中，没有任何一次交换操作发生时，表示数列已经有序，此时可以直接退出循环。

2、在排序过程中，记录最后一次发生交换的位置，之后的数列都已排好序，因此可以减少比较次数：

public class BubbleSortAnimation {

    public static void mAIn(String[] args) {
        int[] arr = {10, 2, 1, 42, 22, 8, 9, 11, 1, 4, 6, 33, 20, 11, 17, 55, 24};
        int n = arr.length;
        int lastExchange = 0; // 最后一次交换位置
        int sortBorder = n - 1; // 无序数列的边界
        for (int i = 0; i < n - 1; i++) {
            boolean flag = true; // 标记是否发生交换
            for (int j = 0; j < sortBorder; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = false; // 发生交换
                    lastExchange = j; // 记录最后一次交换位置
                }
            }

            // 打印每一轮排序后的数组情况
            System.out.print("第 " + (i + 1) + " 轮排序后的数组为：");
            for (int k = 0; k < n; k++) {
                System.out.print(arr[k] + " ");
            }
            System.out.println();

            sortBorder = lastExchange; // 更新无序数列的边界
            if (flag) {
                break; // 本轮排序未发生交换，说明已有序
            }
        }
    }
}

• 1.
• 2.
• 3.
• 4.
• 5.
• 6.
• 7.
• 8.
• 9.
• 10.
• 11.
• 12.
• 13.
• 14.
• 15.
• 16.
• 17.
• 18.
• 19.
• 20.
• 21.
• 22.
• 23.
• 24.
• 25.
• 26.
• 27.
• 28.
• 29.
• 30.
• 31.
• 32.
• 33.

示例代码的输出日志:

第 1 轮排序后的数组为：2 1 10 22 8 9 11 1 4 6 33 20 11 17 42 24 55 
第 2 轮排序后的数组为：1 2 10 8 9 11 1 4 6 22 20 11 17 33 24 42 55 
第 3 轮排序后的数组为：1 2 8 9 10 1 4 6 11 20 11 17 22 24 33 42 55 
第 4 轮排序后的数组为：1 2 8 9 1 4 6 10 11 11 17 20 22 24 33 42 55 
第 5 轮排序后的数组为：1 2 8 1 4 6 9 10 11 11 17 20 22 24 33 42 55 
第 6 轮排序后的数组为：1 2 1 4 6 8 9 10 11 11 17 20 22 24 33 42 55 
第 7 轮排序后的数组为：1 1 2 4 6 8 9 10 11 11 17 20 22 24 33 42 55 
第 8 轮排序后的数组为：1 1 2 4 6 8 9 10 11 11 17 20 22 24 33 42 55

• 1.
• 2.
• 3.
• 4.
• 5.
• 6.
• 7.
• 8.

动图效果:

冒泡排序过程演示，若无法显示动图请刷新重试

四、算法分析

1、时间复杂度：最好情况下为O(n)，即数列已经排序完成，无需进行任何比较操作；最坏情况下为O(n^2)；平均情况下为O(n^2)。

2、空间复杂度：由于只需要一个额外的变量来保存临时变量，并没有使用任何额外的空间，空间复杂度为O(1)。

3、稳定性：冒泡排序是一种稳定排序算法，因为在比较相邻的两个元素时，只有在前一个元素大于后一个元素时才会进行交换，不会改变相同元素之间的顺序。

五、总结

冒泡排序是一种简单而又经典的排序算法，虽然其时间复杂度较高，但由于其实现简单，易于理解，是许多排序算法中最为基础的一种。在实际应用中，我们可以根据具体情况对其进行优化，从而提高算法的效率。