全国咨询/投诉热线:400-618-4000

Java算法之冒泡排序【超详细】

更新时间:2020年06月11日16时41分 来源:传智播客 浏览次数:

学java就到传智播客


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

简单理解: 每次都从第一个元素开始(索引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培训课程

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

精品java视频课程推荐



javaee

python

web

ui

cloud

test

c

netmarket

pm

Linux

movies

robot

uids

北京校区

    14天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    20天免费试学

    基础班入门课程限时免费

    申请试学名额

    8天免费试学

    基础班入门课程限时免费

    申请试学名额

    20天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    0天免费试学

    基础班入门课程限时免费

    申请试学名额

    12天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    10天免费试学

    基础班入门课程限时免费

    申请试学名额