首页技术文章正文

Java冒泡排序算法详细介绍【2020新版】

更新时间:2020-06-11 来源:黑马程序员 浏览量:

冒泡排序基本思想核心思想是从头开始让相邻的两个元素进行比较,符合条件就交换位置,这样就把最大值或者最小值放到数组的最后面了;接着再从头开始两两比较交换,直到把最大值或者最小值放到数组的倒数第二位。(即不需要与最后一位数进行对比).....以此类推,直到排序完成。


简单理解: 每次都从第一个元素开始(索引0),向后两两比较,只要后面的比前面的大,就交换(从大到小) 


用最简单的代码实现冒泡排序对数组进行从大到小的顺序排列: 


int[] array = {3,4,5,6,7}; 

1591864216012_冒泡排序01.jpg


第一趟排序比较的顺序: array[0]和array[1]比较,array[1]和array[2]比较,array[2]和array[3]比较,array[3]和array[4]比较


1591864273624_冒泡排序02.jpg

代码

public class BubbleSort {

    public static void main(String[] args) {

        //定义数组

        int[] array = {3,4,5,6,7};

        //从索引为0开始依次向后两两比较,总共比较4次

        for(int i = 0;i<4;i++) {

            if(array[i]<array[i+1]) {    //只要后面的比它大就交换

                int temp = array[i];

                array[i] = array[i+1];

                array[i+1] = temp;

            }

        }

        System.out.println("第一趟排序后:"+Arrays.toString(array));

    }

}



运行结果

第一趟排序后:[4, 5, 6, 7, 3]



第二趟排序

比较的顺序:array[0]和array[1]比较,array[1]和array[2]比较,array[2]和array[3]比较


1591864299365_冒泡排序03.jpg

代码

在第一趟排序的BubbleSort类中,添加如下代码片段:


//从索引为0开始依次向后两两比较,总共比较3次

for(int i = 0;i<3;i++) {

    if(array[i]<array[i+1]) {    //只要后面的比它大就交换

        int temp = array[i];

        array[i] = array[i+1];

        array[i+1] = temp;

    }

}

System.out.println("第二趟排序后:"+Arrays.toString(array));



运行结果

第二趟排序后:[5, 6, 7, 4, 3]



第三趟排序

比较的顺序:array[0]和array[1]比较,array[1]和array[2]比较

1591864316682_冒泡排序04.jpg

代码

在第二趟排序的BubbleSort类中,添加如下代码片段:


//从索引为0开始依次向后两两比较,总共比较2次

for(int i = 0;i<2;i++) {

    if(array[i]<array[i+1]) {    //只要后面的比它大就交换

        int temp = array[i];

        array[i] = array[i+1];

        array[i+1] = temp;

    }

}

System.out.println("第三趟排序后:"+Arrays.toString(array));


运行结果

第三趟排序后:[6, 7, 5, 4, 3]



第四趟排序

比较的顺序:array[0]和array[1]比较


代码

在第三趟排序的BubbleSort类中,添加如下代码片段:


//从索引为0开始依次向后两两比较,总共比较1次

for(int i = 0;i<1;i++) {

    if(array[i]<array[i+1]) {    //只要后面的比它大就交换

        int temp = array[i];

        array[i] = array[i+1];

        array[i+1] = temp;

    }

}

System.out.println("第四趟排序后:"+Arrays.toString(array));


运行结果

第四趟排序后:[7, 6, 5, 4, 3]


找出共性优化冒泡排序代码

以上代码,我们发现对于5个数字的排序我们用了简单的4个for循环就可以完成,而且每个for循环的内容都差不多,这样可以对以上4个for循环的内容进行变化,很容易看出里面的共性的内容,从而更方便的简化代码.每个for循环的初始化条件都是i=0,for循环中的内容都是相同的. 只有结束条件不同: 

第一个for的结束条件是<4;第二个for循环的结束条件<3;第三个for循环的结束条件<2;第四个for循环的结束条件<1;我们发现4正好是数组的长度-1,这样可以进行如下优化: 第一个for的结束条件是<array.length-1-0 ,二个for循环的结束条件<array.length-1-1,第三个for循环的结束条件<array.length-1-2,第四个for循环的结束条件<array.length-1-3这样四个for循环的结束条件唯一不同的就是最后减的数字不同(其实真正的含义是每一趟排序都会确定出一个数字的具体的位置,下一趟排序,就可以少排一个)

(注意:其实最后减的数字可以不写的,写上是为了提高效率,但是前面的array.length-1中的-1不能省略,是为了防止索引越界异常,因为我们进行比较的时候,分别用i和i+1作为索引获取数组中的元素,所以要保证i和i+1都不能越界,所以i必须<array.length-1)

代码

public class BubbleSort {


    public static void main(String[] args) {


        //定义数组


        int[] array = {3,4,5,6,7};


        //从索引为0开始依次向后两两比较


        for(int i = 0;i<array.length‐1‐0;i++) {


            if(array[i]<array[i+1]) {    //只要后面的比它大就交换


                int temp = array[i];


                array[i] = array[i+1];


                array[i+1] = temp;


            }


    }


    System.out.println("第一趟排序后:"+Arrays.toString(array));


    //从索引为0开始依次向后两两比较,总共比较3次


    for(int i = 0;i<array.length‐1‐1;i++) {


        if(array[i]<array[i+1]) {    //只要后面的比它大就交换


            int temp = array[i];


            array[i] = array[i+1];


            array[i+1] = temp;


        }


    }


    System.out.println("第二趟排序后:"+Arrays.toString(array));


    //从索引为0开始依次向后两两比较,总共比较2次


    for(int i = 0;i<array.length‐1‐2;i++) {


        if(array[i]<array[i+1]) {    //只要后面的比它大就交换


            int temp = array[i];


            array[i] = array[i+1];


           array[i+1] = temp;


         }


    }


    System.out.println("第三趟排序后:"+Arrays.toString(array));


    //从索引为0开始依次向后两两比较,总共比较1次


    for(int i = 0;i<array.length‐1‐3;i++) {


        if(array[i]<array[i+1]) {    //只要后面的比它大就交换


            int temp = array[i];


            array[i] = array[i+1];


            array[i+1] = temp;


        }


    }


    System.out.println("第四趟排序后:"+Arrays.toString(array));


    }


}


运行结果

第一趟排序后:[4, 5, 6, 7, 3]

第二趟排序后:[5, 6, 7, 4, 3]

第三趟排序后:[6, 7, 5, 4, 3]

第四趟排序后:[7, 6, 5, 4, 3]


冒泡排序的最终代码

以上4个for循环代码重复性较高,唯独不一样的地方就是每个for循环结束条件最后减的数字不同,第一个for循环结束条件减的数字是0,第二个for循环结束条件减的数字是1,第3个for循环结束条件减的数字是2,第4个for循环结束条件减的数字是3,这样可以写一个循环4次的for循环,假设循环变量为j,只要j的取值>=0开始到<4结束,正好能获取0,1,2,3的数字,然后把上面的任意一个for循环作为循环体,把该循环体中for循环的结束条件中最后减掉的数字用j替换掉即可.发现5个数只需要排4趟,那么n个数需要排n-1趟,如果上面的循环中的变量j的范围固定写成<4,对于有6,7,...个数字的数组排序是不通用的,所以4可以使用数组的长度array.length-1 = 5-1 来表示


代码

public class BubbleSort {


    public static void main(String[] args) {


    //定义数组


    int[] array = {3,4,5,6,7};


    System.out.println("排序前的内容:"+Arrays.toString(array));


    for(int j = 0;j<array.length‐1;j++) {    //外层循环,趟数


        //j:0,1,2,3


        //i = 0:表示每次都从索引为0的开始,向后两两比较


        for(int i = 0;i<array.length‐1‐j;i++) {


        //内层循环,每趟执行的次数,‐1为了防止索引越界,‐j为了提高效率


            if(array[i]<array[i+1]) {


                int temp = array[i];


                array[i] = array[i+1];


                array[i+1] = temp;


           }


        }


    }


    System.out.println("排序后的内容:"+Arrays.toString(array));


    }


}


运行结果

排序前的内容:[3, 4, 5, 6, 7]

排序后的内容:[7, 6, 5, 4, 3]



总结

1、冒泡排序的原理:每次都从第一个元素开始(索引0),向后两两比较,只要后面的比前面的大,就交换(从大到小)

2、通过画图分析,5个数字排4趟,n数字排n-1趟,而外层的for循环代表的是循环的趟数,所以外层循环的结束条件是array.length-1,但是写array.length代码也没有问题,比如5个数字在第4趟都已经排好了,再进行第5趟排序,也不会影响程序的结果。

3、内层循环变量的初始值写成int i =0,是为了保证每次都从第一个元素开始(索引为0)向后两两比较。但是内层循环的结束条件i<array.length-1-i,这里一定要-1,原因很简单,因为在内层循环中分表使用i和i+1作为索引获取数组的元素,就要保证i和i+1都不能超出数组的索引范围,即i<array.length && i+1<array.length 推导出i<array.length-1.最后的-i只是为了提高效率,因为每趟排序都会确定一个数组元素的位置,下一趟排序的时候,已经确定好位置的元素是不用继续排序的。推荐了解黑马程序员java培训课程

猜你喜欢:
冒泡排序算法动图版

分享到:
在线咨询 我要报名
和我们在线交谈!