面試官：說說你對冒泡排序的理解？如何實現？應用場景？
本文轉載自微信公眾號「JS每日一題」，作者灰灰 。轉載本文請聯系JS每日一題公眾號。
一、是什么
冒泡排序(Bubble Sort)，是一種計算機科學領域的較簡單的排序算法
冒泡排序的思想就是在每次遍歷一遍未排序的數列之后，將一個數據元素浮上去(也就是排好了一個數據)
如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”
假如我們要把 12、35、99、18、76 這 5 個數從大到小進行排序，那么數越大，越需要把它放在前面
思路如下：
- 從后開始遍歷，首先比較 18 和 76，發現 76 比 18 大，就把兩個數交換順序，得到 12、35、99、76、18
- 接著比較 76 和 99，發現 76 比 99 小，所以不用交換順序
- 接著比較 99 和 35，發現 99 比 35 大，交換順序
- 接著比較 99 和 12，發現 99 比 12 大，交換順序
最終第 1 趟排序的結果變成了 99、12、35、76、18，如下圖所示：
上述可以看到，經過第一趟的排序，可以得到最大的元素，接下來第二趟排序則對剩下的的4個元素進行排序，如下圖所示：
經過第 2 趟排序，結果為 99、76、12、35、18
然后開始第3趟的排序，結果為99、76、35、12、18
然后第四趟排序結果為99、76、35、18、12
經過 4 趟排序之后，只剩一個 12 需要排序了，這時已經沒有可比較的元素了，這時排序完成
二、如何實現
如果要實現一個從小到大的排序，算法原理如下：
首先比較相鄰的元素，如果第一個元素比第二個元素大，則交換它們
針對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對，這樣，最后的元素會是最大的數
針對所有的元素重復以上的步驟，除了最后一個
持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較
用代碼表示則如下：
- 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 輪這樣的排序
而在每輪排序中都需要對相鄰的兩個元素進行比較，在最壞的情況下，每次比較之后都需要交換位置，此時時間復雜度為O(n^2)
優化
對冒泡排序常見的改進方法是加入一標志性變量exchange，用于標志某一趟排序過程中是否有數據交換
如果進行某一趟排序時并沒有進行數據交換，則說明數據已經按要求排列好，可立即結束排序，避免不必要的比較過程
可以設置一標志性變量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;
- }
在待排序的數列有序的情況下，只需要一輪排序并且不用交換，此時情況最好，時間復雜度為O(n)
并且從上述比較中看到，只有后一個元素比前面的元素大(小)時才會對它們交換位置并向上冒出，對于同樣大小的元素，是不需要交換位置的，所以對于同樣大小的元素來說，相對位置是不會改變的，因此， 冒泡排序是穩定的
三、應用場景
冒泡排的核心部分是雙重嵌套循環， 時間復雜度是 O(N 2 )，相比其它排序算法，這是一個相對較高的時間復雜度，一般情況不推薦使用，由于冒泡排序的簡潔性，通常被用來對于程序設計入門的學生介紹算法的概念
參考文獻
- 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/
