_冒泡排序和数据结构和算法可视化网站（及其一点小优化）

原创

会洗碗的CV工程师

修改于 2023-11-24 14:53:12

17400

代码可运行

文章被收录于专栏：LongJava学习资料LongJava学习资料

运行总次数：0

代码可运行

一、冒泡排序的原理

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

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

冒泡排序算法的原理如下：

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

冒泡排序就是两两交换，第一趟排序可以得到最大值，那么第二趟排序就不用再比较最大值了，同样是两两交换，找出第二大的值。然后经过n-1次趟的两两比较之后就可以排序完毕了。

比如说现有数组{4，5，7，9，6，3，1，2，1，8}，那么冒泡排序的意思就是

第一趟排序就是现比较4，5，4<5不互换位置，5<7，也不互换位置，7<9，也不用互换位置，9>6，此时6和9互换位置，以此类推，接下来的数字都比9小，都得和9互换位置，总共比较9次，也就是n-1次得出第一趟排序之后的结果就是

4	5	7	6	3	1	2	1	8	9

第二趟排序，由于已经知道最大值了，所以总共比较n-2次即可，得出以下结果：

4	5	6	3	1	2	1	7	8	9

二、动图演示原理

下面就不一一列举了，给一个更加形象生动的图演示一下：

添加描述

三、代码实现：

    public static int[] BS(int [] array){
        int temp;
        for(int i = 0;i<array.length-1;i++){
            for(int j = 0;j<array.length-1-i;j++){
                if(array[j]>array[j+1]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
        return array;
    }

四、优化后的冒泡排序

好了，那现在我们已经知道原理了，能不能做出一点小优化呢，答案是肯定可以的，因为比如说，第一层循环已经固定是length-1次，但是现实生活中有可能不需要排那么多次，在其中排序的过程中就可能已经排好了，此时我们要做的就是消除第一层不必要的排序了。那么我们可以根据if语句是否执行可以判断数组是否已经排好序了，因为如果不执行if语句的话，那肯定是排好序的了，所以此时我们可以在第一层循环里面定义一个标志变量，如果进入if语句就改变该标志变量，第二层循环执行完之后，再判断该标志是否已经被发生变化，如果没有变化，那么就说明已经排好序了，就可以结束循环了。否则，继续进行冒泡排序。

优化后的代码：

    public static int[] A_BS(int [] array){
        int temp;
        for(int i = 0;i<array.length-1;i++){
            boolean flag = true;
            for(int j = 0;j<array.length-1-i;j++){
                if(array[j]>array[j+1]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    flag = false;
                }
            }
            if(flag){
                break;
            }
        }
        return array;
    }