冒泡排序详细详解

因为在面试时  经常手写冒泡排序   可是冒泡排序看起来容易  理解起来也是有点问题   所以今天把冒泡排序的知识点详细的从头整理一下

如果下面的文字不理解   可以参考B站【Java基础入门 冒泡排序】https://www.bilibili.com/video/BV1td4y1g7Fy?vd_source=581d732b20cb23e01428068f153a99ed

我也是用的这个例子

我们以下面的例子为例

题目:

使用冒泡排序，实现整型数组元素的排序操作比如：int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};

分析

我们先比较内层  就是第一轮  每相邻二个元素  交换位置 交换的规则 默认大的放后面 小的放前面

我们如果想实现数组的两两交换的话  我们这里面   我们应该让arr[0]与arr[1]进行比较  大的放在前面  小的放在后面

arr[0]=9

arr[1]=7

如果arr[0]>arr[1]   那么就要进行比较   要进行交换就要引入第三方变量 temp  

所以我们应该写的代码如下 

if(arr[0]>arr[1]){ int temp =arr[0]; arr[0] =arr[1]; arr[1]=temp;}

这时我们的数据就变成

int[] arr = {7,9, 8, 5, 6, 4, 3, 2, 1};

接下去在这个数据的基础上  我们的arr[1]和arr[2]进行比较

arr[1] =9

arr[2] =8

如果arr[1]>arr[1]   那么就要进行比较   要进行交换就要引入第三方变量 temp  

所以我们应该写的代码如下 

if(arr[1]>arr[2]){ int temp = arr[1]; arr[1]   = arr[2]; arr[2]   = temp;}

这时我们的数据就变成

int[] arr = {7,8, 9, 5, 6, 4, 3, 2, 1};

一直相邻比较后  我们就可以求得最大值

由我们的分析  我们每次的代码都是重复  主要是重复的代码 我们就要用到循环  所以我们就可以书写代码如下   完成每轮交换  完成第一轮交换后  9就在最右边   取得最大值

public class BubbleSortTest3 {    public static void main(String[] args) {                int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};        for (int j = 0; j < arr.length; j++) {            if (arr[j] > arr[j + 1]) {                int temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;            }        }    }}

但是我们上面的代码是有错的  

当i取得最大索引的时候  这里我们i的最大索引是8  也就是arr[8]   arr[8]>arr[9]  可是我们并没有9的索引  如果这样写的话  会报如下错误

所以应该写成下面这个样子

public class BubbleSortTest3 {    public static void main(String[] args) {                int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};        for (int j = 0; j < arr.length-1; j++) {            if (arr[j] > arr[j + 1]) {                int temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;            }        }    }}

这样第一轮交换就已经拿到最大值

接下去我们进行第二轮交换

因为第一轮时  最大值已经确定下来了 所以我们不用在比较最大值    所以arr.length-1-1

这样子数组中的元素我们就可以少比较一个

第二轮比较的代码如下 

package com.atguigu4.search_sort.exer3;import java.util.Arrays;public class BubbleSortTest3 {    public static void main(String[] args) {                int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};        //排序前  对数组进行遍历        System.out.println("排序前");        for (int i = 0; i < arr.length; i++) {        }        System.out.println(Arrays.toString(arr));        //排序后        System.out.println("排序后");        //第一轮        System.out.println("第一轮");        for (int j = 0; j < arr.length-1; j++) {            if (arr[j] > arr[j + 1]) {                int temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;            }        }        System.out.println(Arrays.toString(arr));        //第二轮        System.out.println("第二轮");        for (int j = 0; j < arr.length-1-1; j++) {            if (arr[j] > arr[j + 1]) {                int temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;            }        }        System.out.println(Arrays.toString(arr));    }}

以此类推  我们比较8轮

package com.atguigu4.search_sort.exer3;import java.util.Arrays;public class BubbleSortTest3 {    public static void main(String[] args) {                int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};        //排序前  对数组进行遍历        System.out.println("排序前");        for (int i = 0; i < arr.length; i++) {        }        System.out.println(Arrays.toString(arr));        //排序后        System.out.println("排序后");        //第一轮        System.out.println("第一轮");        for (int j = 0; j < arr.length-1-0; j++) {            if (arr[j] > arr[j + 1]) {                int temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;            }        }        System.out.println(Arrays.toString(arr));        //第二轮        System.out.println("第二轮");        for (int j = 0; j < arr.length-1-1; j++) {            if (arr[j] > arr[j + 1]) {                int temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;            }        }        System.out.println(Arrays.toString(arr));        //第三轮        System.out.println("第三轮");        for (int j = 0; j < arr.length-1-2; j++) {            if (arr[j] > arr[j + 1]) {                int temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;            }        }        System.out.println(Arrays.toString(arr));        //第四轮        System.out.println("第二轮");        for (int j = 0; j < arr.length-1-3; j++) {            if (arr[j] > arr[j + 1]) {                int temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;            }        }        System.out.println(Arrays.toString(arr));        //第五轮        System.out.println("第四轮");        for (int j = 0; j < arr.length-1-4; j++) {            if (arr[j] > arr[j + 1]) {                int temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;            }        }        System.out.println(Arrays.toString(arr));        //第六轮        System.out.println("第六轮");        for (int j = 0; j < arr.length-1-5; j++) {            if (arr[j] > arr[j + 1]) {                int temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;            }        }        System.out.println(Arrays.toString(arr));        //第七轮        System.out.println("第七轮");        for (int j = 0; j < arr.length-1-6; j++) {            if (arr[j] > arr[j + 1]) {                int temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;            }        }        System.out.println(Arrays.toString(arr));        //第八轮        System.out.println("第八轮");        for (int j = 0; j < arr.length-1-7; j++) {            if (arr[j] > arr[j + 1]) {                int temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;            }        }        System.out.println(Arrays.toString(arr));    }}

每一轮比较的代码都是重复的   所以我们可以把循环的代码用for循环循环包起来

循环

package com.atguigu4.search_sort.exer3;import java.util.Arrays;public class BubbleSortTest3 {    public static void main(String[] args) {                int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};        //排序前  对数组进行遍历        System.out.println("排序前");        for (int i = 0; i < arr.length; i++) {        }        System.out.println(Arrays.toString(arr));        //排序后        System.out.println("排序后");        for (int i = 0; i < arr.length; i++) {            for (int j = 0; j < arr.length - 1 - i; j++) {                if (arr[j] > arr[j + 1]) {                    int temp = arr[j];                    arr[j] = arr[j + 1];                    arr[j + 1] = temp;                }            }            System.out.println(Arrays.toString(arr));        }//        //第一轮//        System.out.println("第一轮");//        for (int j = 0; j < arr.length-1-0; j++) {////            if (arr[j] > arr[j + 1]) {//                int temp = arr[j];//                arr[j] = arr[j + 1];//                arr[j + 1] = temp;//            }//        }////        System.out.println(Arrays.toString(arr));////////////        //第二轮//        System.out.println("第二轮");//        for (int j = 0; j < arr.length-1-1; j++) {////            if (arr[j] > arr[j + 1]) {//                int temp = arr[j];//                arr[j] = arr[j + 1];//                arr[j + 1] = temp;//            }//        }////        System.out.println(Arrays.toString(arr));//////        //第三轮//        System.out.println("第三轮");//        for (int j = 0; j < arr.length-1-2; j++) {////            if (arr[j] > arr[j + 1]) {//                int temp = arr[j];//                arr[j] = arr[j + 1];//                arr[j + 1] = temp;//            }//        }////        System.out.println(Arrays.toString(arr));////////        //第四轮//        System.out.println("第二轮");//        for (int j = 0; j < arr.length-1-3; j++) {////            if (arr[j] > arr[j + 1]) {//                int temp = arr[j];//                arr[j] = arr[j + 1];//                arr[j + 1] = temp;//            }//        }////        System.out.println(Arrays.toString(arr));////////        //第五轮//        System.out.println("第四轮");//        for (int j = 0; j < arr.length-1-4; j++) {////            if (arr[j] > arr[j + 1]) {//                int temp = arr[j];//                arr[j] = arr[j + 1];//                arr[j + 1] = temp;//            }//        }////        System.out.println(Arrays.toString(arr));//////        //第六轮//        System.out.println("第六轮");//        for (int j = 0; j < arr.length-1-5; j++) {////            if (arr[j] > arr[j + 1]) {//                int temp = arr[j];//                arr[j] = arr[j + 1];//                arr[j + 1] = temp;//            }//        }////        System.out.println(Arrays.toString(arr));////////        //第七轮//        System.out.println("第七轮");//        for (int j = 0; j < arr.length-1-6; j++) {////            if (arr[j] > arr[j + 1]) {//                int temp = arr[j];//                arr[j] = arr[j + 1];//                arr[j + 1] = temp;//            }//        }////        System.out.println(Arrays.toString(arr));////////        //第八轮//        System.out.println("第八轮");//        for (int j = 0; j < arr.length-1-7; j++) {////            if (arr[j] > arr[j + 1]) {//                int temp = arr[j];//                arr[j] = arr[j + 1];//                arr[j + 1] = temp;//            }//        }////        System.out.println(Arrays.toString(arr));//    }}

当第一轮比较的时候  arr.length-1-0   因为谁都不确定  所以都要比较

当第二轮比较的时候  arr.length-1-1  因为最大值已经出来了

当第三轮比较的时候  arr.length-1-2  因为最大值和次大值已经出来了

轮数=元素的总个数-1

因为我们数组的无数有9个 所以我们要比较8轮

因为我们有9个数据（有9个元素）  所以我们要进行8轮交换 所以我们的代码变成如下

package com.atguigu4.search_sort.exer3;import java.util.Arrays;public class BubbleSortTest3 {    public static void main(String[] args) {                int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};        //排序前  对数组进行遍历        System.out.println("排序前");        for (int i = 0; i < arr.length; i++) {        }        System.out.println(Arrays.toString(arr));        //排序后        System.out.println("排序后");        for (int i = 0; i < arr.length - 1; i++) {            for (int j = 0; j < arr.length - 1 - i; j++) {                if (arr[j] > arr[j + 1]) {                    int temp = arr[j];                    arr[j] = arr[j + 1];                    arr[j + 1] = temp;                }            }            System.out.println(Arrays.toString(arr));        }//        //第一轮//        System.out.println("第一轮");//        for (int j = 0; j < arr.length-1-0; j++) {////            if (arr[j] > arr[j + 1]) {//                int temp = arr[j];//                arr[j] = arr[j + 1];//                arr[j + 1] = temp;//            }//        }////        System.out.println(Arrays.toString(arr));////////////        //第二轮//        System.out.println("第二轮");//        for (int j = 0; j < arr.length-1-1; j++) {////            if (arr[j] > arr[j + 1]) {//                int temp = arr[j];//                arr[j] = arr[j + 1];//                arr[j + 1] = temp;//            }//        }////        System.out.println(Arrays.toString(arr));//////        //第三轮//        System.out.println("第三轮");//        for (int j = 0; j < arr.length-1-2; j++) {////            if (arr[j] > arr[j + 1]) {//                int temp = arr[j];//                arr[j] = arr[j + 1];//                arr[j + 1] = temp;//            }//        }////        System.out.println(Arrays.toString(arr));////////        //第四轮//        System.out.println("第二轮");//        for (int j = 0; j < arr.length-1-3; j++) {////            if (arr[j] > arr[j + 1]) {//                int temp = arr[j];//                arr[j] = arr[j + 1];//                arr[j + 1] = temp;//            }//        }////        System.out.println(Arrays.toString(arr));////////        //第五轮//        System.out.println("第四轮");//        for (int j = 0; j < arr.length-1-4; j++) {////            if (arr[j] > arr[j + 1]) {//                int temp = arr[j];//                arr[j] = arr[j + 1];//                arr[j + 1] = temp;//            }//        }////        System.out.println(Arrays.toString(arr));//////        //第六轮//        System.out.println("第六轮");//        for (int j = 0; j < arr.length-1-5; j++) {////            if (arr[j] > arr[j + 1]) {//                int temp = arr[j];//                arr[j] = arr[j + 1];//                arr[j + 1] = temp;//            }//        }////        System.out.println(Arrays.toString(arr));////////        //第七轮//        System.out.println("第七轮");//        for (int j = 0; j < arr.length-1-6; j++) {////            if (arr[j] > arr[j + 1]) {//                int temp = arr[j];//                arr[j] = arr[j + 1];//                arr[j + 1] = temp;//            }//        }////        System.out.println(Arrays.toString(arr));////////        //第八轮//        System.out.println("第八轮");//        for (int j = 0; j < arr.length-1-7; j++) {////            if (arr[j] > arr[j + 1]) {//                int temp = arr[j];//                arr[j] = arr[j + 1];//                arr[j + 1] = temp;//            }//        }////        System.out.println(Arrays.toString(arr));//    }}

所以综合以上分析  我们冒泡排序代码如下：

package com.atguigu4.search_sort.exer3;import java.util.Arrays;public class BubbleSortTest3 {    public static void main(String[] args) {                int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};        //排序前  对数组进行遍历        System.out.println("排序前");        for (int i = 0; i < arr.length; i++) {        }        System.out.println(Arrays.toString(arr));        //排序后        System.out.println("排序后");        for (int i = 0; i < arr.length - 1; i++) {            for (int j = 0; j < arr.length - 1 - i; j++) {                if (arr[j] > arr[j + 1]) {                    int temp = arr[j];                    arr[j] = arr[j + 1];                    arr[j + 1] = temp;                }            }            System.out.println(Arrays.toString(arr));        }    }}

 输出结果如下 ：

也可以把代码封装成一个方法  Ctrl+Alt+M

package com.atguigu4.search_sort.exer3;import java.util.Arrays;public class BubbleSortTest3 {    public static void main(String[] args) {                int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};        //排序前  对数组进行遍历        System.out.println("排序前");        for (int i = 0; i < arr.length; i++) {        }        System.out.println(Arrays.toString(arr));        //排序后        System.out.println("排序后");        sort(arr);    }    private static void sort(int[] arr) {        for (int i = 0; i < arr.length - 1; i++) {            for (int j = 0; j < arr.length - 1 - i; j++) {                if (arr[j] > arr[j + 1]) {                    int temp = arr[j];                    arr[j] = arr[j + 1];                    arr[j + 1] = temp;                }            }           // System.out.println(Arrays.toString(arr));                   }    }}

来源地址：https://blog.csdn.net/m0_59281987/article/details/133937994