一、原理

冒泡排序是相邻的元素两两比较,把小的元素往前调或者把大的元素往后调,实现最大(小)值排列在一端。

注:相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法

二、排序步骤

  1. 对相邻的两个元素进行比较。如果前者比后者大,则交换;反之,不动。
  2. 每趟从第一对相邻元素开始,对每一对相邻元素进行比较,直到最后相邻元素比较完结束。
  3. 针对所有的元素重复以上的步骤,除了已排序过的元素(每趟排序后的最后一个元素)。

引用动态展示:
在这里插入图片描述

三、实现代码

public class Test {
    public static void main(String[] args) {
        int[] arr = {8,2,6,7,5};
        int temp = 0;
        //通过2次循环,外循环控制比较的轮数,内循环控制比较的次数
        for(int i=1;i< arr.length-1;i++){
            for(int j=0;j< arr.length-i;j++){

                if(arr[j] > arr[j+1]){
                    temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        //遍历输出
        System.out.println("随机排序后的数组为:");
        for(int n=0;n< arr.length;n++){
        System.out.print(arr[n]+"\t");
        }
    }
}

运行结果如下:
在这里插入图片描述

四、复杂度分析

最好情况:待排序序列的初始状态恰好是目标排序结果,则一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值:
  此时,冒泡排序的时间复杂度为O(n)
最坏情况:待排序序列和目标排序结果恰好相反,则需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:   
  此时,冒泡排序的时间复杂度为O(n2)
综上,冒泡排序的平均时间复杂度为O(n2)