• 基本思想: 比较两个相邻的元素，将值大的元素交换到右边，雪碧中常常有许多小小的气泡，往上飘，这是因为组成小气泡的二氧化碳比水要轻，所以小气泡才会一点一点的向上浮。而冒泡排序之所以叫冒泡排序
• 直观表达，每一趟遍历，将一个最大的数移到序列末尾。

算法描述

比较相邻的元素，如果前一个比后一个大，交换之。

代码实现

public class BubbleSortMain {
    public static void main(String[] args) {
        Integer[] arr = {2,5,1,3,8,5,7,4,3};
        System.out.println(Arrays.deepToString(arr));  // 排序前
        sortBubble(arr);
        System.out.println(Arrays.deepToString(arr)); // 排序后
    }

    // 冒泡方法
    private static void sortBubble(Integer[] arr) {
        if (arr==null||arr.length<2){
            return;
        }

        for (int i=0;i<arr.length-1;i++){
            for (int j=0;j<arr.length-i-1;j++){
                if (arr[j]>arr[j+1]){
                    int temp= arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
    }
}

冒泡排序时间复杂度

冒泡排序的时间复杂度是O(N2)。
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1次！因此，冒泡排序的时间复杂度是O(N2)。

冒泡排序稳定性

冒泡排序是稳定的算法，它满足稳定算法的定义。
算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！