前言
冒泡排序應(yīng)該是很多小伙伴的最愛，簡(jiǎn)單、直接、好理解；回顧以往參與和閱讀的項(xiàng)目，凡是牽涉自定義排序的算法，很大一部分都在用冒泡，其中很多都忽略了一個(gè)關(guān)鍵點(diǎn)；來，咱們細(xì)細(xì)品...
正文
1. 冒泡排序算法思想
冒泡排序（Bubble Sort）是屬于交換排序的一種，顧名思義，就是一個(gè)元素，依次和相鄰元素進(jìn)行比較(升序或降序)，然后進(jìn)行交換，這個(gè)過程就稱為冒泡。
算法思想
從前往后(或從后往前)依次比較待排序數(shù)據(jù)中相鄰的兩個(gè)元素的值，若符合交換條件，則進(jìn)行交換，直到待排序數(shù)據(jù)比較完，這樣的過程就稱為“一趟”冒泡排序；最終完成排序，最多需要n-1趟排序;（n代表元素個(gè)數(shù)）。
每一趟排序都讓一個(gè)元素移動(dòng)到最終的位置，在之后的冒泡排序中就無需再對(duì)比了。
如果在一趟排序過程中未發(fā)生“交換”，則算法可提前結(jié)束； 這是個(gè)關(guān)鍵，很多小伙伴會(huì)忽略。
2. 冒泡排序算法實(shí)現(xiàn)與解析
代碼實(shí)現(xiàn)(升序)：
運(yùn)行效果如下：
步驟解析(升序)：
上圖步驟說明：
上圖中分三趟排序，每一趟的交換過程根據(jù)箭頭方向進(jìn)行，其中每一行中的綠色方框代表的是當(dāng)趟排序需要交互的數(shù)據(jù)。
第一趟中，對(duì)原始數(shù)據(jù)array開始遍歷，這里使用的是從往后的方式；
第一趟第一步，對(duì)比后面兩個(gè)元素9和3， 9大于3，所以9和3交換位置；
第一趟第二步，對(duì)比相鄰兩個(gè)元素1和3， 1小于3，不需要交換；
第一趟第三步，對(duì)比相鄰兩個(gè)元素6和1， 6大于1，所以6和1交換位置；
第一趟第四步，對(duì)比相鄰兩個(gè)元素5和1， 5大于1，所以5和1交換位置；
第一趟第五步，對(duì)比相鄰兩個(gè)元素2和1， 2大于1，所以2和1交換位置；遍歷完成，第一趟排序結(jié)束，得到結(jié)果1、2、5、6、3、9；這里確定了元素1的最終位置，后續(xù)不在需要對(duì)比了； 代碼實(shí)現(xiàn)是這樣的，但為了好理解，畫圖的時(shí)候都體現(xiàn)了一下。
第二趟排序，接著第一趟的排序結(jié)果進(jìn)行冒泡排序；
第二趟第一步，對(duì)比后面兩個(gè)元素3和9， 3小于9，不需要交換；
第二趟第二步，對(duì)比相鄰兩個(gè)元素6和3， 6大于3，所以6和3交換位置；
第二趟第三步，對(duì)比相鄰兩個(gè)元素5和3，5大于3，所以5和3交換位置；
第二趟第四步，對(duì)比相鄰兩個(gè)元素2和3， 2小于3，不需要交換；
第二趟第五步，對(duì)比相鄰兩個(gè)元素1和2， 1小于2，不需要交換；遍歷完成，第二趟排序結(jié)束，得到結(jié)果1、2、3、5、6、9；其實(shí)這步?jīng)]有，因?yàn)榈谝徊揭呀?jīng)確定了元素1的位置，可以不進(jìn)行比對(duì)；這里只是便于理解虛擬了出這一步。
第三趟排序，接著第二趟排序結(jié)果進(jìn)行冒泡排序；
- 依次比較第二次結(jié)果的數(shù)據(jù)，最后發(fā)現(xiàn)沒有數(shù)據(jù)進(jìn)行交互，則排序結(jié)束，數(shù)據(jù)已經(jīng)排好序；不需要再遍歷，到此，整個(gè)冒泡排序完成；
3. 冒泡排序算法性能分析
時(shí)間復(fù)雜度
時(shí)間復(fù)雜度最壞情況就是待排序數(shù)據(jù)和要的結(jié)果完全逆序，則需要的比較的次數(shù)為：(n-1)+(n-2)+(n-3)+...+1，則最壞的時(shí)間復(fù)雜度為O(n2)。最好的時(shí)間復(fù)雜度就是待排序數(shù)據(jù)和要的結(jié)果完全一致，則比較n-1次即可，則最好的時(shí)間復(fù)雜度為O(n)；所以最后的平均時(shí)間復(fù)雜度為O(n2)。
空間復(fù)雜度 在算法核心部分只采用了固定的幾個(gè)中間變量(i,j,lengh,bChange)，所以算法過程中消耗的內(nèi)存是一個(gè)常量，則空間復(fù)雜度為O(1)；
穩(wěn)定性 由于在排序過程中是通過大于符號(hào)或小于符號(hào)進(jìn)行比較，當(dāng)?shù)扔跁r(shí)是不進(jìn)行位置交換的，所以此算法是穩(wěn)定的。
綜上所述，冒泡排序的時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)，是穩(wěn)定算法；
總結(jié)
冒泡排序關(guān)鍵點(diǎn)一定要注意哦：
每趟排序會(huì)確定一個(gè)元素的最終位置，這個(gè)元素在下一趟排序中可以不進(jìn)行比較了；
如果在一趟排序中沒有發(fā)生數(shù)據(jù)交換，則代表數(shù)據(jù)列表已經(jīng)有序，可以終止排序啦；
從上面可以看出，冒泡排序雖然簡(jiǎn)單，但需要依次遍歷元素進(jìn)行比較，當(dāng)數(shù)據(jù)元素過多時(shí)，比較次數(shù)就越多；那有沒有減少比較次數(shù)的解決方案呢；答案當(dāng)然是肯定的，下期一起來聊聊快速排序。
感謝小伙伴的：點(diǎn)贊、收藏和評(píng)論，下期繼續(xù)~~~
一個(gè)被程序搞丑的帥小伙，關(guān)注"Code綜藝圈"，跟我一起學(xué)~~~
