一、定義

冒泡排序是最基礎(chǔ)的排序算法。

冒泡排序的英文是bubble sort，它是一種基礎(chǔ)的交換排序。

冒泡排序這種排序算法的每一個(gè)元素都可以像小氣泡一樣，根據(jù)自身大小，一點(diǎn)一點(diǎn)地向著數(shù)組的一側(cè)移動(dòng)。

二、思路

按照冒泡排序的思想，我們要把相鄰的元素兩兩比較，當(dāng)一個(gè)元素大于右側(cè)相鄰元素時(shí)，交換它們的位 置；當(dāng)一個(gè)元素小于或等于右側(cè)相鄰元素時(shí)，位置不變。

經(jīng)過第一輪后： 元素9作為數(shù)列中最大的元素，就像是汽水里的小氣泡一樣，“漂”到了最右側(cè)。

每一輪結(jié)束都會(huì)有一個(gè)元素被移到最右側(cè)。

三、實(shí)現(xiàn)

1、冒泡算法

public static void main(String[] args) {
    int[] array = {1,6,2,5,3,0,3,5,4};
    array = bubbleSortBySortedExchanged(array);
    for(int i =0 ; i < array.length; i++){
        System.out.println(array[i]);
    }

}

    public static int[] bubbleSort(int[] array){
        //有array.length-1個(gè)數(shù)字需要交換
        for(int i = 0; i < array.length - 1; i++){
            //每個(gè)數(shù)字比較的次數(shù)是array.length-1-i
            for(int j = 0; j < array.length - 1 - i; j++){
                //如果當(dāng)前值大于后一個(gè)值，則將更大的值移到后一位
                if(array[j] > array[j+1]){
                    swap(array[j],array[j+1]);
                }
            }
        }
        return array;
    }

   //互相交換值
    public static void swap(int a,int b){
        int temp = a;
        a  = b;
        b  = temp;
    }

2、冒泡算法優(yōu)化

（1）外層優(yōu)化

第6輪已經(jīng)可以結(jié)束了，也就是如果不需要交換了，則說明已經(jīng)排好序了

思路：在外層循環(huán)處，設(shè)置標(biāo)志isSort，默認(rèn)為排好，如果不交換則跳出本次循環(huán)

（2）內(nèi)部優(yōu)化

已經(jīng)被移到右側(cè)的元素不用再參與比較了

思路：設(shè)置lastExchangeIndex標(biāo)志單輪比較中最后一次比較的數(shù)值下標(biāo)，下一輪比較就以lastExchangeIndex結(jié)束。

private static  int[] bubbleSortBySortedExchanged(int[] array){
    if(array == null || array.length < 2){
        return array;
    }
    //單輪比較中最后一次交換的數(shù)值下標(biāo)
    int lastExchangeIndex = 0;
    int sortBorder = array.length - 1;
    //不交換則表示已排好
    boolean isSorted = true;
    for(int i = 0 ;i < array.length - 1; i++){
        for(int j = 0; j < sortBorder ; j++){
            if(array[j] > array[j+1]){
                isSorted = false;
                int temp = array[j+1];
                array[j+1] = array[j];
                array[j] = temp;
                lastExchangeIndex = j;
            }
        }
        sortBorder = lastExchangeIndex;
        if(isSorted){
            break;
        }
    }
    return array;
}

四、復(fù)雜度

時(shí)間復(fù)雜度：O( n的2次方 )

空間復(fù)雜度：O(1)，也就是原地排序

穩(wěn)定性:相等元素之間原有的先后順序不變，也就是穩(wěn)定排序