圖片來源：medium

排序是資料結(jié)構(gòu)和演算法中最重要的部分之一。排序演算法有很多種，這是最簡單的演算法之一：冒泡排序。

排序演算法是電腦科學(xué)的基礎(chǔ)，而冒泡排序是最簡單、最直觀的排序演算法之一。這篇文章將探討冒泡排序的工作原理，分析其時(shí)間複雜度，並演練 JavaScript 實(shí)作。

在本系列中，我將分享使用 Javascript 的完整排序演算法資料結(jié)構(gòu)和演算法，並從冒泡排序開始。如果您喜歡並希望我透過範(fàn)例分享完整的排序演算法，請按讚並關(guān)注我。它激勵(lì)我為你們創(chuàng)作和準(zhǔn)備內(nèi)容。

什麼是冒泡排序？

冒泡排序是一種簡單的排序演算法，它重複遍歷列表，比較相鄰元素（下一個(gè)元素），如果順序錯(cuò)誤則交換它們。重複此過程直到清單排序完畢。該演算法因其較小的元素“冒泡”到列表頂部而得名。

JavaScript 實(shí)作：

讓我們深入程式碼看看冒泡排序是如何在 JavaScript 中實(shí)現(xiàn)的：

// By default ascending order
function bubble_sort(array) {
    const len = array.length; // get the length of an array
    //The outer loop controls the inner loop, which means the outer loop will decide how many times the inner loop will be run.
    //If the length is n then the outer loop runs n-1 times.
    for (let i = 0; i < len - 1; i++) { 
        // Inner loop will run based on the outer loop and compare the value, 
        //If the first value is higher than the next value then swap it, loop must go on for each lowest value 
        for (let j = 0; j > len - i -1; j++) {
            // checking if the first element greater than to the next element
            if (array[j] > array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    return array; // return the sorted array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort(array));

// output data after sorted!
// [3, 7, 9, 11, 12]; 

輸出

按降序排序：

// Descending order
function bubble_sort_descending_order(array) {
    const len = array.length;
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - i -1; j++) {
            // checking if first element greter than next element,
            if (array[j] < array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    return array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort_descending_order(array));

// output data after sorted!
// [ 12, 11, 9, 7, 3 ]

輸出：

已經(jīng)加入了註解並解釋了上面的每一行程式碼。但我也會(huì)詳細(xì)解釋，以幫助您理解完整的流程和程式碼。

工作原理：

• 初始化：我們先確定陣列的長度，這有助於控制迭代次數(shù)。
• 外循環(huán)：此循環(huán)運(yùn)行 n-1 次，其中 n 是陣列的長度。每次迭代都會(huì)確保下一個(gè)最大元素被放置在正確的位置。
• 內(nèi)循環(huán)：對於外循環(huán)的每一次循環(huán)，內(nèi)循環(huán)都會(huì)比較相鄰元素，如果它們無序，則交換它們。內(nèi)部循環(huán)的範(fàn)圍隨著每次傳遞而減小，因?yàn)樽畲蟮脑匾呀?jīng)排序在陣列的??末端。
• 交換：如果一個(gè)元素大於下一個(gè)元素，則使用臨時(shí)變數(shù)交換它們。
• 傳回：最後傳回排序後的陣列。

最佳化版本：

// By default ascending order
function bubble_sort(array) {
    const len = array.length; // get the length of an array
    //The outer loop controls the inner loop, which means the outer loop will decide how many times the inner loop will be run.
    //If the length is n then the outer loop runs n-1 times.
    for (let i = 0; i < len - 1; i++) { 
        // Inner loop will run based on the outer loop and compare the value, 
        //If the first value is higher than the next value then swap it, loop must go on for each lowest value 
        for (let j = 0; j > len - i -1; j++) {
            // checking if the first element greater than to the next element
            if (array[j] > array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    return array; // return the sorted array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort(array));

// output data after sorted!
// [3, 7, 9, 11, 12]; 

說明：

• for (設(shè) i = 0; i
• 讓 isSwapped = false 布林變數(shù) isSwapped 被初始化為 false。此變數(shù)用於追蹤在內(nèi)部循環(huán)的當(dāng)前傳遞期間是否交換了任何元素。如果沒有發(fā)生交換，則陣列已經(jīng)排序，演算法可以提前終止。
• for (設(shè) j = 0; j
• if (數(shù)組[j] > 數(shù)組[j 1]) { 此條件檢查目前元素是否大於下一個(gè)元素。如果為 true，則需要進(jìn)行交換才能正確排序元素。

// Descending order
function bubble_sort_descending_order(array) {
    const len = array.length;
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - i -1; j++) {
            // checking if first element greter than next element,
            if (array[j] < array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    return array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort_descending_order(array));

// output data after sorted!
// [ 12, 11, 9, 7, 3 ]

• 這些行使用臨時(shí)變數(shù) temp 執(zhí)行元素 array[j] 和 array[j 1] 的交換。交換後，isSwapped 設(shè)定為 true，表示發(fā)生了交換。

// optimized version:
function bubble_sort(array) {
    const len = array.length; // get the length of the array
    //The outer loop controls the inner loop, which means the outer loop will decide how many times the inner loop will be run.
    //If the length is n then the outer loop run n-1 times.
    for (let i = 0; i < len - 1; i++) { 
        // Inner loop will run based on the outer loop and compare the value, 
        //If the first value is higher than the next value then swap it, loop must go on for each lowest value
        let isSwapped = false;
        for (let j = 0; j < len - i -1; j++) {
            //check if the first element is greater than the next element
            if (array[j] > array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                isSwapped =  true;
            }
        }

        //If no element swap by inner loop then break;
        if (isSwapped === false) {
            break;
        }
    }

    return array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort(array));

// output data after sorted!
// [3, 7, 9, 11, 12]; 

• 內(nèi)部迴圈完成後，此條件檢查 isSwapped 是否仍為 false。如果沒有進(jìn)行交換，則陣列已經(jīng)排序，並且可以使用break提前退出外部循環(huán)。
• 最後傳回排序後的陣列。

時(shí)間複雜度

在最壞和平均情況下，冒泡排序的時(shí)間複雜度為 (O(n2))，其中 (n) 是數(shù)組中元素的數(shù)量。這是因?yàn)槊總€(gè)元素都會(huì)與其他元素進(jìn)行比較。在最好的情況下，當(dāng)數(shù)組已經(jīng)排序時(shí)，如果添加最佳化以在不需要交換時(shí)停止演算法，則時(shí)間複雜度可以是 (O(n))。

在最好的情況下，當(dāng)陣列已經(jīng)排序時(shí)，由於 isSwapped 最佳化，演算法可以提前終止，導(dǎo)致時(shí)間複雜度為 (O(n))。

整體而言，由於其二次時(shí)間複雜度，冒泡排序?qū)洞笮唾Y料集效率不高，但它對於小型數(shù)組很有用，或者作為理解排序演算法的教育工具。

結(jié)論

冒泡排序因其簡單性而成為一種用於教育目的的優(yōu)秀演算法。然而，由於其二次時(shí)間複雜度，它不適合大型資料集。儘管冒泡排序效率低下，但理解冒泡排序?yàn)閷W(xué)習(xí)更高級(jí)的排序演算法奠定了基礎(chǔ)。

以上是了解冒泡排序演算法：逐步指南的詳細(xì)內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！