1.復(fù)雜度與穩(wěn)定性

算法時間復(fù)雜度

最壞情況：O(n^2)

最好情況：O(n)

平均情況：O(n^2)

空間復(fù)雜度：S(n)=O(1)

穩(wěn)定性：穩(wěn)定排序

2.過程介紹（以順序?yàn)槔?/span>

1.從第一個元素開始逐個比較相鄰的元素。如果第一個比第二個大（a[1]>a[2]），就交換他們兩個。

2.對每一對相鄰元素做同樣的工作，從開始第一對到結(jié)尾的最后一對。此時在這一點(diǎn)，最后的元素應(yīng)該會是最大的數(shù)，我們也稱呼一遍這樣的操作為：一趟冒泡排序。

3.針對所有的元素重復(fù)以上的步驟，每一趟冒泡排序的最大值已放在最后，下一次操作則不需要將此最大值納入計(jì)算計(jì)算。

4.持續(xù)對每次對越來越少的元素，重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較，即完成冒泡排序。

3.圖示過程

以數(shù)組數(shù)據(jù){ 70,50,30,20,10,70,40,60}為例：

如此圖，每一次排序結(jié)尾，總有一個最大的數(shù)被放在了最后，然后這個趨勢逐漸往前，但是，到了第四趟的時候，其實(shí)我們整個數(shù)據(jù)已經(jīng)排序結(jié)束了，但是此時我們的程序還在進(jìn)行，直到第5，6，7趟結(jié)束程序才算真正的結(jié)束，這其實(shí)是一種浪費(fèi)算力的表現(xiàn)。

4.相關(guān)的代碼

#include<iostream>
using namespace std;
void bubble_sort(int a[],int n) {
    for(int i=0; i<n; i++) {
        for(int j=0; j<n-i; j++) {
            if(a[j]>a[j+1]) {
                swap(a[j],a[j+1]);  //交換數(shù)據(jù)
            }
        }
    }
}
 
int main() {
    int a[8]= {70,50,30,20,10,70,40,60};
    int n=7;
    bubble_sort(a,n);
    for(int i=0; i<=n; i++) {
        cout<<a[i]<<' ';
    }
    return 0;
}

在這里提示一下，由于C++的namespace std命名空間的使用，std自帶了交換函數(shù)swap(a,b)，我們可以直接使用，其功能是交換a與b的兩個值，在教程后面的排序中會經(jīng)常用到，當(dāng)然你可以自定義swap函數(shù)，其模板代碼為：

template<class T>        //模板類，可以讓參數(shù)為任意類型
void swap(T &a,T &b) {
    T c(a);
    a=b;
    b=c;
}

或者指定類型修改為整形，如：

void swap(int &a, int &b) { //指定類型
    int temp = a;
    a = b;
    b = temp;
}

那么我們的冒泡排序就算學(xué)完了，其實(shí)冒泡排序是八大排序中最簡單及基礎(chǔ)的排序，這個算法的名字由來是因?yàn)樵酱蟮脑貢?jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。