今天要介紹的是另一種排序算法限匣，冒泡排序。冒泡排序和快速排序一樣毁菱，都是屬于交換排序米死，也就是都是通過判斷某種條件，對(duì)數(shù)組進(jìn)行交換操作贮庞，實(shí)現(xiàn)排序的算法峦筒。

對(duì)很多計(jì)算機(jī)專業(yè)的童鞋來說，冒泡排序算法應(yīng)該是他們上在大學(xué)課堂上接觸的第一種排序算法窗慎。大多數(shù)高校的計(jì)算機(jī)專業(yè)的第一門程序設(shè)計(jì)課應(yīng)該都是C語言物喷，我還記得是講完流程控制語句和循環(huán)語句之后書中的一個(gè)例子介紹的就是冒泡排序算法。因?yàn)槊芭菟惴ň秃退拿忠粯诱诔猓浅５男蜗舐褪В判蜻^程很好理解，也不像快速排序那樣术吗，實(shí)現(xiàn)起來需要調(diào)用數(shù)組和日期的方法尉辑，以及遞歸的思想，掌握起來不那么容易藐翎。冒泡排序只需要簡(jiǎn)單邏輯判斷語句以及循環(huán)語句就可以輕松實(shí)現(xiàn)材蹬。縱觀八種排序算法吝镣，冒泡排序應(yīng)該是最容易實(shí)現(xiàn)最容易理解的排序算法堤器。

雖然冒泡排序的實(shí)現(xiàn)很簡(jiǎn)單，但是在日常開發(fā)中很少使用末贾，因?yàn)樗钠骄鶗r(shí)間復(fù)雜度為O（n2）闸溃，這個(gè)和快速排序的nlg（n）時(shí)間復(fù)雜度相差太多，如果待排序的數(shù)組是千萬級(jí)的上億級(jí)的數(shù)據(jù)規(guī)模拱撵，那么進(jìn)行一次的冒泡排序比快速排序多耗費(fèi)的時(shí)間無疑是巨大的辉川。不管對(duì)C端還是B端的用戶來說，過長(zhǎng)的時(shí)間查詢都是極差的用戶體驗(yàn)拴测，如果在淘寶上輸入一個(gè)搜索條件乓旗，幾秒鐘都沒有出結(jié)果我相信可能很少有人會(huì)選擇繼續(xù)等待。因此對(duì)網(wǎng)站來說集索，效率就是生命屿愚，時(shí)間就是金錢汇跨。

即使冒泡排序的效率低，耗費(fèi)的時(shí)間長(zhǎng)妆距，但是任何東西都有正反兩面穷遂，世界上一切的存在都是合理的，再優(yōu)秀的人也有弱點(diǎn)娱据，再平庸的人也有擅長(zhǎng)的一面蚪黑。而冒泡排序也不例外，它是一個(gè)穩(wěn)定的排序算法中剩，而快速排序算法是不穩(wěn)定的排序算法忌穿。在排序中的所謂的穩(wěn)定性指的是，如果在數(shù)組中兩個(gè)值相等结啼，則在排序之后不會(huì)改變這兩個(gè)值的位置伴网，這個(gè)是快速排序不具備的，如果兩個(gè)元素相等的時(shí)候妆棒，冒泡排序不會(huì)進(jìn)行交換澡腾，但是快速排序僅僅通過基準(zhǔn)進(jìn)行判斷，在有些情況下會(huì)對(duì)相等的元素進(jìn)行交換糕珊。廢話不多說了动分，下面開始介紹冒泡排序的算法和實(shí)現(xiàn)。

上一篇博客我把快速排序歸納為兩個(gè)步驟红选，那么以簡(jiǎn)單著稱的冒泡排序只需要用一步就可以實(shí)現(xiàn)：

1澜公、從數(shù)組的第一個(gè)開始兩兩比較，如果前面的元素大于后面的元素喇肋，兩個(gè)元素交換坟乾。

2、忽略最后一個(gè)元素蝶防，重復(fù)第一步甚侣。

雖然這兩句話看起來簡(jiǎn)單明了，但是我還是要舉一個(gè)例子间学，形象的解釋一下這個(gè)過程：

待排序數(shù)組：[3,2,1];

第一遍處理：[2,3,1]——>[2,1,3]

第二遍處理：[1,2,3]

可以看見殷费，第一遍處理的時(shí)候，3和2進(jìn)行比較低葫，3比2大详羡，3和2交換，然后3和1進(jìn)行比較嘿悬，3大于1,3和1進(jìn)行交換实柠。這時(shí)候，數(shù)組中最大的元素善涨，被移動(dòng)到了最后一位窒盐，這就是第一遍的效果茶行，而第二遍，2和1進(jìn)行比較登钥，2比1大，2和1進(jìn)行交換娶靡，然后由于最大的就是3牧牢，不需要交換。這樣第二大的元素被放到了倒數(shù)第二位姿锭，還剩一個(gè)1自然就是最小的元素塔鳍。整個(gè)排序的過程就和一個(gè)氣泡從一個(gè)試管里浮上來，而最大的元素就是那個(gè)氣泡呻此，其他的元素構(gòu)成了這個(gè)試管轮纫。我覺得有的時(shí)候，千言萬語都趕不上一段代碼來的實(shí)在焚鲜，這也許就是說和做的區(qū)別掌唾，接下來我就來介紹一下冒泡排序算法的代碼實(shí)現(xiàn)。

首先定義一個(gè)排序函數(shù)忿磅，接收一個(gè)待排序的數(shù)組作為參數(shù)糯彬，如果數(shù)組的長(zhǎng)度小于二直接將數(shù)組返回。

function bubbleSort(arr) {

? if(arr.length<2){

? ? return arr;

? ?}

}

準(zhǔn)備工作做完下面進(jìn)行第一步：從數(shù)組的第一個(gè)開始兩兩比較葱她，如果前面的元素大于后面的元素撩扒，兩個(gè)元素交換和第二步：忽略最后一個(gè)元素，重復(fù)第一步吨些。

這一步中需要解釋的有兩個(gè)部分搓谆，首先需要解釋的是兩個(gè)元素進(jìn)行交換的操作，原理很簡(jiǎn)單豪墅，定義一個(gè)空的元素泉手，用來做兩個(gè)元素的中間變量，就好比現(xiàn)在有兩個(gè)球偶器，分別在你的左手和右手螃诅，要將這兩個(gè)球從你的雙手交換位置，但是一個(gè)手只允許放一個(gè)球状囱，這個(gè)時(shí)候你需要第三個(gè)容器先把左手的球放到容器里术裸，再把右手的球放到左手里，然后用右手拿起容器里面的球亭枷，這樣就實(shí)現(xiàn)了左右手球的交換操作袭艺。

接下來是嵌套的for循環(huán)，剛才介紹算法的時(shí)候叨粘，舉的例子[3,2,1]猾编，第一遍是兩次交換瘤睹，第二遍是一次交換。第三遍是0次交換答倡。在程序中轰传，外層循環(huán)控制的就是排序算法的操作的遍數(shù)，而內(nèi)層循環(huán)控制的才是真正每遍循環(huán)需要進(jìn)行交換操作的次數(shù)瘪撇，通過簡(jiǎn)單的觀察可以看出這樣的規(guī)律获茬，每次交換的次數(shù)=數(shù)組的長(zhǎng)度-第幾遍，在兩次for循環(huán)之后就得到了排序之后的數(shù)組倔既。雖然解釋的不那么標(biāo)準(zhǔn)和官方恕曲，但是真的懂了就是最好的。接下來是代碼實(shí)現(xiàn)渤涌，這個(gè)時(shí)候不得不小小的吐槽一下簡(jiǎn)書的富文本編輯器佩谣，在這上面敲代碼好難，還是截圖吧实蓬。

雖然在代碼量上并沒有比快速排序少很多茸俭，但是算法的復(fù)雜度上，實(shí)現(xiàn)的難度上確實(shí)簡(jiǎn)單很多安皱。

關(guān)于冒泡排序的算法就介紹到這瓣履，接下來聊點(diǎn)題外話。接下來聊點(diǎn)我的一點(diǎn)小想法练俐，可能不太成熟袖迎，希望前輩大神們批評(píng)指正，在上面我舉的第一個(gè)例子腺晾，[3,2,1]燕锥，數(shù)組的長(zhǎng)度為3，第一遍處理進(jìn)行了兩次交換操作悯蝉，第二遍處理進(jìn)行了一次交換操作归形。一共1+2次交換鼻由。試想一下暇榴，如果數(shù)組的長(zhǎng)度為4蕉世，一共會(huì)進(jìn)行3+2+1次交換操作蔼紧。就在寫這篇博客的時(shí)候狠轻，看到了這兩串?dāng)?shù)字奸例，就讓我想起了高中學(xué)過的數(shù)學(xué)知識(shí)，等差數(shù)列向楼，每次的交換次數(shù)恰恰是等差數(shù)列的求和公式查吊，

在算法中，假設(shè)n為無窮大逻卖，n在n2面前可以忽略不計(jì)所以n+n2就是n2，而1/2*n2也就是n2评也，因此炼杖，可以得出如果要進(jìn)行冒泡排序最壞的情況下需要進(jìn)行n2次交換操作，所以時(shí)間復(fù)雜度為O（n2）仇参。這也許是比較另類的冒泡排序算法的時(shí)間復(fù)雜度的推導(dǎo)方式。

寫完了兩篇博客婆殿，最大的感受是覺得自己收獲了真的很多，漸漸發(fā)現(xiàn)婆芦，分享真的是很美好的，在寫博客的過程中會(huì)彌補(bǔ)很多自己的知識(shí)漏洞消约，提升自己，在寫完第一篇快速排序算法的當(dāng)天晚上或粮，連做夢(mèng)都在寫那一段代碼。把一件事情講明白氯材，自己也就很透徹的明白了，比讀書氢哮，查資料真的要高效的多。如果在博客中有錯(cuò)誤冗尤，或者不足都希望前輩們批評(píng)指正。