文中大部分內(nèi)容為摘抄自網(wǎng)友文章裕便，只供個(gè)人學(xué)習(xí)和備忘。

算法思想

它重復(fù)地走訪過(guò)要排序的數(shù)列见咒，一次比較兩個(gè)元素偿衰，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成下翎。

算法步驟

1. 比較相鄰的元素缤言。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)视事。
2. 對(duì)每一對(duì)相鄰元素作同樣的工作胆萧，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)郑口，最后的元素應(yīng)該會(huì)是最大的數(shù)鸳碧。
3. 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)犬性。
4. 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟瞻离，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

算法復(fù)雜度

時(shí)間復(fù)雜度

若文件的初始狀態(tài)是正序的乒裆，一趟掃描即可完成排序套利。所需的關(guān)鍵字比較次數(shù) C 和記錄移動(dòng)次數(shù) M 均達(dá)到最小值：Cmin=n-1,Mmin=0著瓶。
所以也祠，冒泡排序最好的時(shí)間復(fù)雜度為:O(n)舔株。
若初始文件是反序的找前，需要進(jìn)行n-1趟排序。每趟排序要進(jìn)行n-i次關(guān)鍵字的比較(1≤i≤n-1)缝裁，且每次比較都必須移動(dòng)記錄三次來(lái)達(dá)到交換記錄位置铛只。在這種情況下跟磨，比較和移動(dòng)次數(shù)均達(dá)到最大值：

空間復(fù)雜度

在交換時(shí)需要申請(qǐng)一個(gè)變量族购，固空間復(fù)雜度為O(1)

算法穩(wěn)定性

冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較陵珍，交換也發(fā)生在這兩個(gè)元素之間寝杖。所以，如果兩個(gè)元素相等互纯，我想你是不會(huì)再無(wú)聊地把他們倆交換一下的瑟幕；如果兩個(gè)相等的元素沒(méi)有相鄰，那么即使通過(guò)前面的兩兩交換把兩個(gè)相鄰起來(lái)留潦，這時(shí)候也不會(huì)交換只盹，所以相同元素的前后順序并沒(méi)有改變，所以冒泡排序是一種穩(wěn)定排序算法兔院。

算法描述（JAVA）

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

算法優(yōu)化

優(yōu)化1：

設(shè)置一個(gè)標(biāo)記來(lái)標(biāo)志一趟排序是否發(fā)生了交換操作殖卑，如果沒(méi)有發(fā)生則代表數(shù)組已經(jīng)有序。

public void bubbleSort(int[] arr){
        int tmp = 0;
        boolean swap = true;
        for (int i = 0; i < arr.length; ++i) {
            swap = true;
            for (int j = 0; j < arr.length - i - 1; ++j) {
                if (arr[j] < arr[j + 1]) {
                    swap = false;
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
            if(swap == true){
                break;
            }
        }
    }

優(yōu)化2：

用一個(gè)變量記錄下最后一個(gè)發(fā)生交換的位置秆乳，后面沒(méi)有發(fā)生交換的已經(jīng)有序懦鼠，所以可以用這個(gè)值來(lái)作為下一次比較結(jié)束的位置。

public void bubbleSort2(int[] arr){
        int tmp = 0;
        int flag = arr.length;
        int m = 0;
        for (int i = 0; i < flag; ++i) {
            m = flag;
            flag = 0;
            for (int j = 0; j < m - 1; ++j) {
                if (arr[j] > arr[j + 1]) {
                    flag = j;
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    }

參考文章：

1. 冒泡排序及兩種優(yōu)化方式
2. 冒泡排序·百度百科