冒泡排序（Java语言）

1.定义

比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

2.代码实现

package day03;

public class bubbleSort {
    public static void main(String[] args) {
        //外层循环进行length-1躺比较
        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];  //temp用来临时存储，作为第三方交换变量。
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}
           

3.时间复杂度

算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大，冒泡排序的最坏时间复杂度为 O(n²)，最好O(n），即一次循环后就退出。

4.动画演示

 5.排序优化

上面实现的代码简单适合用于需要排序的对象无序或近乎无序，当待排序的数组时候，已经有序，或者近乎有序的时候，我们这段代码仍然需要移动很多趟，这对资源来说是一种浪费。

package day03;
public class bubblesort {
    public static void main(String[] args) {
        int[] arr={1,4,5,2,6,8,4,5};
        int end=arr.length-1;
        for (;0<=end;end--){
            //添加flag作为是不是已经有序的判断条件
            boolean falg=true;
            for (int start=0;start<end;start++){
                if (arr[start]>arr[start+1]){
                    int temp=arr[start];
                    arr[start]=arr[start+1];
                    arr[start+1]=temp;
                    falg=false;
                }
            }
            //如果flag等于true就说明数组已经有序了，
            // 在这一轮没有进入交换环节，所以退出循环
            if (falg==true){
                break;
            }
        }
        for (int i=0;i< arr.length;i++){
            System.out.println(arr[i]);
        }
    }
}
           

6.冒泡排序优缺点

优点:比较简单，空间复杂度较低，稳定性高。

缺点:时间复杂度太高，效率慢。