什么是冒泡排序

冒泡排序是一種簡單的排序算法。一次比較兩個(gè)相鄰的元素值，如果它們的順序錯(cuò)誤就把它們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。

此過程類似水里的氣泡，從水底到水面的氣泡越來越大。顧名思義叫做冒泡排序

算法原理

1. 將相鄰的兩個(gè)數(shù)組元素值進(jìn)行比較。如果第一個(gè)元素值比第二個(gè)元素值大，就交換兩個(gè)元素值的位置。?

2. 對(duì)相鄰元素值對(duì)都做同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這樣，最后的元素值就是最大的數(shù)。?

3. 重復(fù)以上的步驟 (除了最后一個(gè)元素值)。?

4. 持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何元素值對(duì)需要比較

冒泡排序的作用

將數(shù)組元素值從小到大排序，解決桶排序浪費(fèi)空間問題

交換數(shù)組元素的方法

方法一：使用第三方變量

方法二：使用es6的解構(gòu)賦值

示例：

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

例如示例中數(shù)組元素?cái)?shù)量為11個(gè)

當(dāng)i=0時(shí)，排序要經(jīng)過11-1次比較

當(dāng)i=1時(shí)，排序要經(jīng)過11-2次比較

當(dāng)i=2時(shí)，排序要經(jīng)過11-3次比較

.......

.......

.......

當(dāng)i=7時(shí)，排序要經(jīng)過11-8次比較

當(dāng)i=8時(shí)，排序要經(jīng)過11-9次比較

當(dāng)i=9時(shí)，排序要經(jīng)過11-10次比較

如果將上面的元素個(gè)數(shù)轉(zhuǎn)換成數(shù)量n

累加：(n-1)+(n-2)+(n-3)+........+3+2+1=（n^2-n）/2 ? (這里要感謝高斯同學(xué).....)

根據(jù)計(jì)算時(shí)間復(fù)雜度的方法，結(jié)果最高次冪為n^2/2

所以冒泡排序的時(shí)間復(fù)雜度為O(n^2)

當(dāng)輸入的數(shù)據(jù)已經(jīng)是正序時(shí)

最差時(shí)間復(fù)雜度 T(n) = O(n2)

當(dāng)輸入的數(shù)據(jù)是反序時(shí)(如果是這種，就反向操作吧)

空間復(fù)雜度

由于在排序過程中僅僅用到了一個(gè)可以重復(fù)使用的臨時(shí)變量 temp ，用于交換兩個(gè)相鄰元素值的中轉(zhuǎn)站，所以空間復(fù)雜度是個(gè)常數(shù)為O(1)