你不知道的「冒泡排序」

前言

冒泡排序

基本概念

冒泡排序在計算機語言中是一個常用的簡單排序。簡而言之，就是數組中相鄰兩個元素進行比較，如果順序不匹配，就依次交換各自的位置，直到數組中所有的數據符合要求為止。

簡單的冒泡排序

<code>    var test = [5, 7, 6, 3, 2]
    function bubbleSort(arr) {
        for (let i=0, len = arr.length; i < len; i++) {
            for (let j = i + 1; j < len; j++) {
                if (arr[i] > arr[j]) {
                    let temp = arr[i]
                    arr[i] = arr[j]
                    arr[j] = temp
                }
            }
        }
    }
    bubbleSort(test)
    console.log(test)/<code>

帶過濾條件的冒泡排序

稍微增加一點處理，假如冒泡排序不是相鄰的比較，是不間斷的比較，該如何處理呢？比如一個數組[5, -1, 6, -8, 10, 2, -9, 11],要求負數的位置不變，只比較正數的位置。 其實原理是一樣的，中間額外加一些判斷條件就可以了，具體代碼如下所示：

<code>    let test = [5, -1, 6, -7, 10, 2, -5, 11]
    function bubbleSort (arr) {
        for (let i=0, len = arr.length; i  
< len; i++) {
            if (arr[i] < 0) continue
            for (let j = i + 1; j < len; j++) {
                if (arr[j] < 0) continue
                if (arr[i] > arr[j]) {
                    let temp = arr[i]
                    arr[i] = arr[j]
                    arr[j] = temp
                }
            }
        }
    }
    bubbleSort(test)
    console.log(test)/<code>

帶延時執行的冒泡排序

上述兩種情況相對比較簡單，屬於入門級的，現在加深下難度，假如每隔一秒，冒泡排序交換一次，這種代碼該怎麼去改呢？ 博主不才，第一想到的竟然是利用閉包，閉包雖好，但是也不能亂用，顯然這種場景下是不合時宜的。閉包能解決的問題是實現塊級作用域，並不能影響代碼的執行時序。雖然能做到每隔一秒執行一次變換排序，但是排序的結果是不對的。錯誤的代碼如下所示：

• 錯誤的方法

<code>let test = [11, -1, 6, 5, -4, -7, 9, 8]
function bubbleSort(arr) {
    let count = 0
    for (let i=0, len = arr.length; i < len; i++) {
        if (arr[i] < 0) continue
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < 0) continue
            if (arr[i] > arr[j]) {
                count++
                (function (i, j) {
                    setTimeout(function() {
                        let temp = arr[i]
                        arr[i] = arr[j]
                        arr[j] = temp
                        console.log(arr)
                    }, count * 1000)
                })(i, j)
            }
        }
    }
}
bubbleSort(test)/<code>

• 原因分析 細心的童鞋可能會發現，閉包傳參沒問題，問題是出現在
  交換的判斷條件裡，循環執行是同步的，但是交換方法不是同步的，每次判斷都是拿原數組數據去判斷，在執行替換操作時，實際上已經修改了原數組的次序，導致後面的替換操作執行是錯的。有一種很簡單的修改方法，就是藉助async/await，實現異步代碼同步執行，具體實現方法如下：
• 正確的寫法

<code>let arr = [11, -1, 6, 5, -4, -7, 9, 8]
async function bubbleSort (arr) {
    for (let i=0, len = arr.length; i < len; i++) {
        if (arr[i] < 0) continue
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < 0) continue
            if (arr[i] > arr[j]) {
                await execute(i, j, arr)
                console.log(arr)
            }
        }
    }
}

function execute (i, j, arr) {
    return new Promise((resolve, reject) => {
        setTimeout(() => {
            let temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
            resolve()
        }, 1000);
    })
}/<code>

關鍵字: function continue temp