Day26--冒泡排序

冒泡排序无疑是最为出名的排序算法之一：总共有八大排序！

冒泡的代码还是相当简单的，两层循环：外层冒泡轮数，里层依次比较：江湖中人人尽皆知。

我们看到嵌套循环：应该立马就可以得出这个算法的时间复杂度为 O (n²)。思考：如何优化？

1. 冒泡排序的思路理解：

一、冒泡排序的起名由来：

冒泡排序的主要思想是通过多次遍历要排序的数列，每次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。

这样经过多次遍历，最大（或最小）的元素就会像气泡一样 “浮” 到数列的顶端。

二、具体过程

1. 第一轮遍历：
   • 从数列的第一个元素开始，依次比较相邻的两个元素。
   • 如果前一个元素比后一个元素大，就交换它们的位置。
   • 这样在第一轮遍历结束后，最大的元素就会被 “冒泡” 到数列的最后一个位置。
2. 第二轮遍历：
   • 由于最大的元素已经在最后位置，所以第二轮遍历只需要对前面的 n - 1 个元素进行操作。
   • 重复第一轮的比较和交换过程，将第二大的元素 “冒泡” 到数列的倒数第二个位置。
3. 依此类推：
   • 每一轮遍历都将未排序部分中的最大元素 “冒泡” 到相应位置。
   • 经过 n - 1 轮遍历后，整个数列就完成了排序。

三、示例说明

假设有一个整数数列 [8, 5, 2, 4, 3]。

1. 第一轮遍历：

   • 比较 8 和 5，因为 8 > 5，所以交换位置，数列变为 [5, 8, 2, 4, 3]。

   • 比较 8 和 2，交换位置，变为 [5, 2, 8, 4, 3]。

   • 比较 8 和 4，交换位置，变为 [5, 2, 4, 8, 3]。

   • 比较 8 和 3，交换位置，变为 [5, 2, 4, 3, 8]。此时第一轮遍历结束，最大的元素 8 被 “冒泡” 到了最后位置。

2. 第二轮遍历：

   • 比较 5 和 2，交换位置，变为 [2, 5, 4, 3, 8]。

   • 比较 5 和 4，交换位置，变为 [2, 4, 5, 3, 8]。

   • 比较 5 和 3，交换位置，变为 [2, 4, 3, 5, 8]。第二轮结束，第二大的元素 5 被 “冒泡” 到了倒数第二个位置。

     和第一轮相比，少了一次比较

3. 第三轮遍历：

   • 比较 2 和 4，不交换位置，数列仍为 [2, 4, 3, 5, 8]。

   • 比较 4 和 3，交换位置，变为 [2, 3, 4, 5, 8]。第三轮结束，第三大的元素 4 被 “冒泡” 到了相应位置。

     和第二轮相比，少了一次比较

4. 第四轮遍历：

   • 比较 2 和 3，不交换位置，数列保持 [2, 3, 4, 5, 8] 不变。第四轮结束，整个数列完成排序。

     和第三轮相比，少了一次比较

四、具体分析

从第二轮遍历开始，每一轮遍历，都比上一轮少一次比较。

每一轮遍历，都会产生出一个最大或者最小的数，排在最前面或者最后面，因此比较次数少一次

遍历的轮数：array.length-1

五、时间复杂度和空间复杂度

元素个数：n； 遍历轮数： i

1. 时间复杂度：

   • 最坏情况下，即数列是逆序的，需要进行 n - 1 轮遍历，每一轮遍历都要比较和交换 n - i 次（i 表示当前轮数），所以总的比较和交换次数为 n (n - 1)/2，时间复杂度为 O (n²)。
   • 最好情况下，即数列已经是有序的，只需要进行一轮遍历就可以完成排序，时间复杂度为 O (n)。不过这种情况出现的概率较低。

2. 空间复杂度：

   • 冒泡排序是一种原地排序算法，只需要常数级别的额外空间，所以空间复杂度为 O (1)。

3. 时间复杂度的理解：以冒泡排序为例：

   在计算机科学中，时间复杂度为 O (n²) 表示算法的运行时间与输入数据规模 n 的平方成正比。

   具体来说，当输入数据规模为 n 时，算法的执行时间可以用一个包含 n² 的表达式来近似表示。例如，如果一个算法对于规模为 n 的输入数据需要执行 n² 次基本操作，那么这个算法的时间复杂度就是 O (n²)。

   以冒泡排序为例，它有两层循环，外层循环执行 n - 1 次（n 为待排序数据的数量），内层循环在每一轮外层循环中执行的次数逐渐减少，但总体上也与 n 相关。对于一个包含 n 个元素的列表进行冒泡排序，大约需要比较和交换的次数为 n (n - 1)/2，当 n 很大时，这个数量级接近 n²，所以冒泡排序的时间复杂度为 O (n²)。

n (n - 1)/2的计算：

n-1+n-2+n-3+...+n-n=n*n-(1+2+...+n)=n *2 n/2-n (n + 1)/2=n/2 * (n-1)

2.冒泡排序的示例

从小到大排序

package com.liu.www.array;

import java.util.Arrays;

public class ArrayDemo07 {
    public static void main(String[] args) {
        int[] a={1,3,2};
        sort(a);
        System.out.println(Arrays.toString(a));


    }
    //冒泡排序
    //1. 比较两个相邻的元素大小。不行就交换位置，来满足：大的排后边，小的排前面
    //2. 每一轮遍历，都会产生出一个最大或者最小的数
    //3.下一轮可以少一次比较
    //4.以此类推，直到结束


    //下面的方法是从小往大排序
    public static int[] sort(int[] array){
        int temp=0;
        //外层循环：判断循环的次数
        for (int i = 0; i < array.length-1; i++) {
            //内层循环：比较两个数的位置。如果第一个数比第二个数大，则交换位置
            for (int j = 1; j <array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    temp=array[j+1];
                    array[j+1]=array[j];
                    array[j]=temp;
                }
            }
        }return array;

    }
    /*
    1 4 2 3   arrays.length=4                     i=0;i<3    j=0;j<3
    1    4                         1423                      j=0;j<3
    4    2--->   2     4           1243                      j=1;j<3
    4    3--->   3     4           1234                      j=2;j<3

     */
}

优化：

当已经排好序的时候，就可以节省遍历次数了

//下面的方法是从小往大排序
    public static int[] sort(int[] array){
        int temp=0;
        boolean flag=true;//通过flag标识符，减少没有意义的比较
        //外层循环：判断循环的次数
        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+1];
                    array[j+1]=array[j];
                    array[j]=temp;
                    flag=false;
                }
                if(flag==true){
                    break;
                }
            }
        }return array;

    }

通过flag标识符，减少没有意义的比较。