基本思想

冒泡排序简单来说就是每一趟排序比较相邻两个元素值，大的交换到后面，那么一趟排序下来最大的元素被沉到最后。对剩下的元素重复以上操作，每一趟都将最大的元素沉到最后，直到所有元素有序。

代码实现

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

时间复杂度

• 最好情况：O(n)，若待排序序列全部有序，则只需进行一趟比较，若没有元素交换则结束排序。
• 平均情况：O(n*n)

算法改进

1. 前面我们说到，冒泡排序在最好的情况下时间复杂度是O(n)，但事实上前面贴的代码在元素全部有序的情况下时间复杂度依然是O(n*n)，因为一趟排序下来我们并不知道这趟排序元素有没有交换。因此，我们需要添加一个标记位来标记一趟排序元素是否有交换。

public void bubbleSort(int[] a){
        int temp;
        boolean flag;
        for(int i = 0; i < a.length - 1; i++){
            flag = false;
            for(int j = 0; j < a.length - 1 - i; j++){
                if(a[j] > a[j + 1]){
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    flag = true;
                }
            }
            if(flag == false){
                break;
            }
        }
    }

2. 再做进一步的优化。如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。

public void bubbleSort(int[] a){
        int temp;
        int lastSwapPos = a.length - 1;
        int lastSwapPosTemp;
        for(int i = 0; i < a.length - 1; i++){
            lastSwapPosTemp = lastSwapPos;
            for(int j = 0; j < lastSwapPosTemp; j++){
                if(a[j] > a[j + 1]){
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    lastSwapPos = j;
                }
            }
            if(lastSwapPosTemp == lastSwapPos){
                break;
            }
        }
    }