[[427403]]

本文轉(zhuǎn)載自微信公眾號「JS每日一題」，作者灰灰 。轉(zhuǎn)載本文請聯(lián)系JS每日一題公眾號。

一、是什么

冒泡排序(Bubble Sort)，是一種計算機科學領(lǐng)域的較簡單的排序算法

冒泡排序的思想就是在每次遍歷一遍未排序的數(shù)列之后，將一個數(shù)據(jù)元素浮上去(也就是排好了一個數(shù)據(jù))

如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”

假如我們要把 12、35、99、18、76 這 5 個數(shù)從大到小進行排序，那么數(shù)越大，越需要把它放在前面

思路如下：

• 從后開始遍歷，首先比較 18 和 76，發(fā)現(xiàn) 76 比 18 大，就把兩個數(shù)交換順序，得到 12、35、99、76、18
• 接著比較 76 和 99，發(fā)現(xiàn) 76 比 99 小，所以不用交換順序
• 接著比較 99 和 35，發(fā)現(xiàn) 99 比 35 大，交換順序
• 接著比較 99 和 12，發(fā)現(xiàn) 99 比 12 大，交換順序

最終第 1 趟排序的結(jié)果變成了 99、12、35、76、18，如下圖所示：

上述可以看到，經(jīng)過第一趟的排序，可以得到最大的元素，接下來第二趟排序則對剩下的的4個元素進行排序，如下圖所示：

經(jīng)過第 2 趟排序，結(jié)果為 99、76、12、35、18

然后開始第3趟的排序，結(jié)果為99、76、35、12、18

然后第四趟排序結(jié)果為99、76、35、18、12

經(jīng)過 4 趟排序之后，只剩一個 12 需要排序了，這時已經(jīng)沒有可比較的元素了，這時排序完成

二、如何實現(xiàn)

如果要實現(xiàn)一個從小到大的排序，算法原理如下：

首先比較相鄰的元素，如果第一個元素比第二個元素大，則交換它們

針對每一對相鄰元素做同樣的工作，從開始第一對到結(jié)尾的最后一對，這樣，最后的元素會是最大的數(shù)

針對所有的元素重復(fù)以上的步驟，除了最后一個

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

用代碼表示則如下：

function bubbleSort(arr) { 
    const len = arr.length; 
    for (let i = 0; i < len - 1; i++) { 
        for (let j = 0; j < len - 1 - i; j++) { 
            if (arr[j] > arr[j+1]) {        // 相鄰元素兩兩對比 
                var temp = arr[j+1];        // 元素交換 
                arr[j+1] = arr[j]; 
                arr[j] = temp; 
            } 
        } 
    } 
    return arr; 
} 

可以看到：冒泡排序在每一輪排序中都會使一個元素排到一趟， 也就是最終需要 n-1 輪這樣的排序

而在每輪排序中都需要對相鄰的兩個元素進行比較，在最壞的情況下，每次比較之后都需要交換位置，此時時間復(fù)雜度為O(n^2)

優(yōu)化

對冒泡排序常見的改進方法是加入一標志性變量exchange，用于標志某一趟排序過程中是否有數(shù)據(jù)交換

如果進行某一趟排序時并沒有進行數(shù)據(jù)交換，則說明數(shù)據(jù)已經(jīng)按要求排列好，可立即結(jié)束排序，避免不必要的比較過程

可以設(shè)置一標志性變量pos，用于記錄每趟排序中最后一次進行交換的位置，由于pos位置之后的記錄均已交換到位，故在進行下一趟排序時只要掃描到pos位置即可，如下：

function bubbleSort1(arr){ 
 const i=arr.length-1;//初始時,最后位置保持不變   
 while(i>0){ 
  let pos = 0;//每趟開始時,無記錄交換 
  for(let j = 0; j < i; j++){ 
   if(arr[j] > arr[j+1]){ 
        let tmp = arr[j]; 
        arr[j] = arr[j+1]; 
        arr[j+1] = tmp; 
    pos = j;//記錄最后交換的位置   
   }    
  } 
  i = pos;//為下一趟排序作準備 
 } 
 return arr; 
} 

在待排序的數(shù)列有序的情況下，只需要一輪排序并且不用交換，此時情況最好，時間復(fù)雜度為O(n)

并且從上述比較中看到，只有后一個元素比前面的元素大(小)時才會對它們交換位置并向上冒出，對于同樣大小的元素，是不需要交換位置的，所以對于同樣大小的元素來說，相對位置是不會改變的，因此， 冒泡排序是穩(wěn)定的

三、應(yīng)用場景

冒泡排的核心部分是雙重嵌套循環(huán)， 時間復(fù)雜度是 O(N 2 )，相比其它排序算法，這是一個相對較高的時間復(fù)雜度，一般情況不推薦使用，由于冒泡排序的簡潔性，通常被用來對于程序設(shè)計入門的學生介紹算法的概念

參考文獻

• https://baike.baidu.com/item/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F/4602306
• https://www.runoob.com/w3cnote/bubble-sort.html
• http://data.biancheng.net/view/116.html
• https://dsb123dsb.github.io/2017/03/07/js%E5%AE%9E%E7%8E%B0%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F%E4%BB%A5%E5%8F%8A%E4%BC%98%E5%8C%96/