<返回更多

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

2023-05-06  今日头条  Code404
加入收藏

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

一、算法原理

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

假设要排序的数列为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 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、时间复杂度:最好情况下为O(n),即数列已经排序完成,无需进行任何比较操作;最坏情况下为O(n^2);平均情况下为O(n^2)。

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

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

五、总结

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

声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍相关推荐
更多资讯 >>>