【校招VIP】数据结构与算法：冒泡排序- 校招VIP

转载声明：文章来源https://blog.csdn.net/weixin_48524739/article/details/126130620

所谓冒泡排序，其实就是按趟比较，第一趟的时候通过比较将最大的数放到最后一位，第二趟再将最大的数放到倒数第二位，依此类推，直到最后全部放置完毕为止。

该图是网上借鉴的，表达的非常直观，就是通过比较将最大的值依次放到最后，具体代码如下所示。

1.不妨一趟一趟的来看结果，最终总结规律即可，首先看第一趟：

package demo;
 
import java.util.Arrays;
 
public class BubbleSort {
 
    public static void main(String[] args) {
 
 
        int[] arr = {10,8,12,6,20,14,17};
 
        //定义一个临时变量，用来存放数据
        int temp = 0;
 
        //第一趟
        for(int j=0;j<arr.length-1;j++){
 
            //arr[j]与arr[j+1]进行比较
            if(arr[j] > arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        System.out.println("第一躺结果：");
        System.out.println(Arrays.toString(arr));
 
    }
 
}

最终得到的第一趟结果：

可以看到，第一趟将最大值20放到了最后。

接着进行第二趟，第三趟：

package demo;
 
import java.util.Arrays;
 
public class BubbleSort {
 
    public static void main(String[] args) {
 
 
        int[] arr = {10,8,12,6,20,14,17};
 
        //定义一个临时变量，用来存放数据
        int temp = 0;
 
        //第一趟
        for(int j=0;j<arr.length-1;j++){
 
            //arr[j]与arr[j+1]进行比较
            if(arr[j] > arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        System.out.println("第一躺结果：");
        System.out.println(Arrays.toString(arr));
 
 
         //第二趟
        for(int j=0;j<arr.length-1-1;j++){  //第二趟趟数又变少了一次，所以再减去1
 
            //arr[j]与arr[j+1]进行比较
            if(arr[j] > arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        System.out.println("第二躺结果：");
        System.out.println(Arrays.toString(arr));
 
        //第三趟
        for(int j=0;j<arr.length-1-1-1;j++){  //第三趟趟数又变少了一次，所以再减去1
 
            //arr[j]与arr[j+1]进行比较
            if(arr[j] > arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        System.out.println("第三躺结果：");
        System.out.println(Arrays.toString(arr));
 
    }
 
}

结果：

可以看到，后三位成功将最大的三位放到了正确的位置，接下来依次进行，知道将所有的数都拍完为止，我这里列举的数不太好，到第三次已经完成从小到大的排列了，但是并不代表第三次就结束了，还需要继续向下比较。

通过这三趟不难发现其中的规律，就是随着趟数的增加，for循环中的长度也要依次减一，不妨再添加一个for循环，将趟数也作为一个变量，这样就可以实现整个过程，具体如下：

package demo;
 
import java.util.Arrays;
 
public class BubbleSort {
 
    public static void main(String[] args) {
 
        int[] arr = {10,8,12,6,20,14,17};
 
        System.out.println("排序前");
        System.out.println(Arrays.toString(arr));
 
        bubbleSort(arr);
 
        System.out.println("排序后");
        System.out.println(Arrays.toString(arr));
 
 
    }
 
    public static void bubbleSort(int[] arr){
        //定义一个临时变量，用来存放数据
        int temp = 0;
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<arr.length-1-i;j++){
 
                //arr[j]与arr[j+1]进行比较
                if(arr[j] > arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
 
}

优化：

给个flag做标记，默认为false, 若趟中没有数据进行交换，则直接退出循环。

package demo;
 
import java.util.Arrays;
 
public class BubbleSort {
 
    public static void main(String[] args) {
 
        int[] arr = {10,8,12,6,20,14,17};
 
        System.out.println("排序前");
        System.out.println(Arrays.toString(arr));
 
        bubbleSort(arr);
 
        System.out.println("排序后");
        System.out.println(Arrays.toString(arr));
 
 
    }
 
    public static void bubbleSort(int[] arr){
        //定义一个临时变量，用来存放数据
        int temp = 0;
        boolean flag = false;
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<arr.length-1-i;j++){
 
                //arr[j]与arr[j+1]进行比较
                if(arr[j] > arr[j+1]){
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            if(!flag){
                break;
            }else {
                flag = false; //进行下次比较需要先将其改成false
            }
        }
    }
 
}

至此整个的冒泡排序结束，引起其是嵌套for循环，所以其复杂度为O(n^2)，后续整理其他排序算法时，可以对他们的复杂度进行一个比较，从而来看哪种算法较好。

通过冒泡排序，可以先跑几趟，最后得出整体规律，相同的，后续其他排序算法都可以通过该方法来进行总结归纳，最终得出其规律。