JavaScript >> Javascript 文檔 >  >> JavaScript

JavaScript 中的冒泡排序和雞尾酒搖酒排序

簡介

冒泡排序 ,有時也稱為下沉排序 是最廣為人知的排序算法之一。它通常是 CS 學生最先遇到的排序算法之一,因為它簡單,而且非常直觀且易於轉換為代碼。

然而,這種簡單的算法在實際問題中表現不佳。尤其是與快速排序或合併排序等更快、更流行和廣泛使用的算法相比。這就是為什麼冒泡排序主要用作教育工具的原因。

在本文中,我們將解釋冒泡排序的工作原理並在 JavaScript 中實現它。我們還將檢查它的時間複雜度,並將其與其他一些排序算法進行比較。

此外,我們將實現它的一種變體 - Cocktail Shaker Sort 試圖對其進行優化。

冒泡排序

冒泡排序是一種比較型排序算法。這意味著它比較 運行時集合中的各個元素。根據您的數據類型和目的,可以通過關係運算符或自定義比較函數進行比較。

冒泡排序背後的想法相當簡單。從我們想要排序的集合的開頭開始 - 我們比較一對中的元素。如果該對處於所需的順序,我們什麼也不做。如果不是,我們交換它所包含的元素。

這是一次又一次地完成,直到集合中的所有元素都被排序。讓我們看一下冒泡排序如何工作的直觀表示:

查看值為 8 的元素 ,我們可以看到它從數組的開頭“冒泡”到正確的位置。這就是“冒泡排序”之名的由來。

冒泡排序實現

現在我們已經了解了冒泡排序背後的想法,我們可以從實現開始:

function bubbleSort(inputArr) {
    let n = inputArr.length;
    
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < n; j++) {
            // Comparing and swapping the elements
            if(inputArr[j] > inputArr[j+1]){
                let t = inputArr[j];
                inputArr[j] = inputArr[j+1];
                inputArr[j+1] = t;
            }
        }
    }
    return inputArr;
}

實現非常直觀。我們遍歷數組n for 的次數 循環,其中 n 是數組的長度。對於每次迭代,我們將一個元素“冒泡”到正確的位置。這是通過另一個 for 完成的 循環將元素與其相鄰元素進行比較,並在需要時切換它們。

最後,我們返回排序後的數組。讓我們填充一個數組並對其進行排序:

let inputArr = [5,1,4,2,8];
bubbleSort(inputArr);
console.log(inputArr);

運行此代碼將產生:

(5) [1, 2, 4, 5, 8]

讓我們看看這是如何使用具體值完成的:

第一次迭代:

[5 , 1 , 4, 2, 8] -> [1 , 5 , 4, 2, 8] - 我們交換 5 和 1,因為 5> 1
[1, 5 , 4 , 2, 8] -> [1, 4 , 5 , 2, 8] - 我們正在交換 5 和 4,因為 5> 4
[1, 4, 5 , 2 , 8] -> [1, 4, 2 , 5 , 8] - 我們正在交換 5 和 2,因為 5> 2
[1, 4, 2, 5 , 8 ] -> [1, 4, 2, 5 , 8 ] - 沒有變化,因為 5 <8

第二次迭代:

[1 , 4 , 2, 5, 8] -> [1 , 4 , 2, 5, 8] - 沒有變化,因為 1 <4
[1, 4 , 2 , 5, 8] -> [1, 2 , 4 , 5, 8] - 我們交換 4 和 2,因為 4> 2
[1, 2, 4 , 5 , 8] -> [1, 2, 4 , 5 , 8] - 沒有變化,因為 4 <5
[1, 2, 4, 5 , 8 ] -> [1, 2, 4, 5 , 8 ] - 沒有變化,因為 5 <8

數組在兩次迭代中排序,但是,我們的算法將繼續運行 n 次,一遍又一遍地比較所有元素。這是因為我們告訴它迭代 inputArr.length 次。

冒泡排序本身效率低下——尤其是有這樣的缺陷。不過,我們可以做兩件事來優化它。

優化

我們可以實現的第一個優化是 - 如果數組已排序,則終止算法 - 即不進行交換。這可以通過 boolean 來完成 旗幟。每次我們交換任何元素時,它都會設置為 true

function bubbleSort(inputArr) {
    let n = inputArr.length;
    let sorted = false;
        
    while (!sorted) {
        sorted = true;
        for(let i = 0; i < n; i++){
            if(inputArr[i] > inputArr[i+1]){
                let t = inputArr[i];
                inputArr[i] = inputArr[i+1];
                inputArr[i+1] = t;
                sorted = false;
            }
        }
    }
    return inputArr;
}

一旦我們完成對數組的迭代,並且沒有進行交換,while 循環將停止循環並返回數組。

讓我們再次填充數組並對其進行排序:

let inputArr = [5,1,4,2,8];
bubbleSort(inputArr);
console.log(inputArr);

此代碼導致:

[1, 2, 4, 5, 8]

免費電子書:Git Essentials

查看我們的 Git 學習實踐指南,其中包含最佳實踐、行業認可的標準以及隨附的備忘單。停止谷歌搜索 Git 命令並真正學習 它!

值得注意的是,第一次迭代完成後,最大的元素將位於數組的末尾。下一次迭代會將第二大元素放在最大元素之前,以此類推。

這意味著在每次迭代中,我們真的不需要查看最後一個元素,因為我們知道它在正確的位置。因此,在 k-th 迭代,我們只需要看看n-k+1 迭代:

function bubbleSort(inputArr) {
        
    let n = inputArr.length;
    let sorted = false;
    let numOfIterations = 0;
        
    while(!sorted) {
        sorted = true;
        for(let i = 0; i < n-numOfIterations+1; i++){
            if(inputArr[i] > inputArr[i+1]){
                let t = inputArr[i];
                inputArr[i] = inputArr[i+1];
                inputArr[i+1] = t;
                sorted = false;
                numOfIterations++;
            }
        }
    }  
    return inputArr;
}

讓我們再次填充數組並對其進行排序:

let inputArr = [5,1,4,2,8];
bubbleSort(inputArr);
console.log(inputArr);

此代碼導致:

(5) [1, 2, 4, 5, 8]

雞尾酒搖床排序與冒泡排序

冒泡排序的另一個優化是它的衍生變體,稱為 雞尾酒搖床排序 ,也稱為雙向冒泡排序 或者乾脆雞尾酒排序 .

該算法通過在兩個方向上操作來擴展冒泡排序。它不是從頭到尾,然後重複,而是從頭到尾,然後從頭到尾,在一個完整的迭代中。實際上,它在一次完整迭代中完成了冒泡排序的兩倍工作,儘管在實踐中它通常不會快兩倍。

這是因為它具有相似的比較計數。與常規冒泡排序相比,它每次迭代比較的元素更多,並且每次迭代的交換次數加倍。它更快的原因是因為每次迭代可能的交換範圍越來越小,從而使其性能稍好。

讓我們繼續執行算法:

function cocktailShakerSort(inputArr) {

    let n = inputArr.length;
    let sorted = false;

    while (!sorted) {
        sorted = true;
        for (let i = 0; i < n - 1; i++) {
            if (inputArr[i] > inputArr[i + 1]){
               let tmp = inputArr[i];
               inputArr[i] = inputArr[i + 1];
               inputArr[i+1] = tmp;
               sorted = false;
            }
   }

   if (sorted)
       break;
   sorted = true;

        for (let j = n - 1; j > 0; j--) {
            if (inputArr[j-1] > inputArr[j]) {
                let tmp = inputArr[j];
                inputArr[j] = inputArr[j + 1];
                inputArr[j+1] = tmp;
                sorted = false;
            }
        }
    }
    return inputArr;
}

第一部分與常規冒泡排序相同。但是,在我們向前通過之後,我們會向後退。首先,我們檢查數組是否使用之前的前向傳遞進行排序。如果沒有,我們就倒退,必要時交換。如果沒有進行交換,則終止算法並返回結果。

如果我們在第二遍中沒有檢查交換,我們將不得不向前傳遞額外的時間來驗證數組是否已排序。

讓我們看一下之前的手動示例——這次是使用雞尾酒搖床:

[5 , 1 , 4, 2, 8] -> [1 , 5 , 4, 2, 8] - 我們交換 5 和 1,因為 5> 1
[1, 5 , 4 , 2, 8] -> [1, 4 , 5 , 2, 8] - 我們正在交換 5 和 4,因為 5> 4
[1, 4, 5 , 2 , 8] -> [1, 4, 2 , 5 , 8] - 我們正在交換 5 和 2,因為 5> 2
[1, 4, 2, 5 , 8 ] -> [1, 4, 2, 5 , 8 ] - 沒有變化,因為 5 <8
[1, 4, 2 , 5 , 8] -> [1, 4, 2 , 5 , 8] - 沒有變化,因為 5> 2
[1, 4 , 2 , 5, 8] -> [1, 2 , 4 , 5, 8] - 我們交換 4 和 2,因為 2 <4
[1 , 2 , 4, 5, 8] -> [1 , 2 , 4, 5, 8] - 沒有變化,因為 2> 1

在這裡,我們的數組在 1 次迭代內排序,與冒泡排序的 2 次迭代不同。雞尾酒排序用 7 次比較來做到這一點,而冒泡排序用 8 次比較來做到這一點。在這個規模上這並不算多,儘管數量更大,我們會看到性能提升。

Donald E. Knuth 在他著名的專著“計算機編程的藝術”中提到了雞尾酒搖晃排序以及一些類似的冒泡排序變體 :

時間複雜度和比較

由於我們的數組包含 n 元素,冒泡排序執行O(n) 比較,n 次。這導致我們的總運行時間為 O(n 2 ) - 平均和最壞情況。這對於排序算法來說是一個可怕的時間複雜度。

作為參考,最常見的排序算法,例如快速排序或合併排序,平均運行時間為 O(nlogn) .

理論上,冒泡排序可以有一個 O(n) 複雜性,如果我們在排序的集合上運行它,它會優於 all 除插入排序和立方體排序外的其他算法。不過,這種情況的罕見性並不能證明在實踐中使用它是合理的。

使用內置的 console.time() 函數,我們可以比較一下在不同長度的數組上運行代碼所需要的時間:

console.time('bubble');
bubbleSort(inputArr);
console.timeEnd('bubble');

我們將對大小為 100 的數組執行此操作 , 100010 000

元素個數 未優化的冒泡排序 帶有“布爾”標誌的冒泡排序 n-k+1 次冒泡排序 雞尾酒搖床排序
100 2ms 1 毫秒 1 毫秒 1 毫秒
1000 8ms 6ms 1 毫秒 1 毫秒
10 000 402 毫秒 383ms 2ms 1 毫秒

顯而易見的是,與 Cocktail Shaker 等變體相比,第一個實現的效率是多麼低。

結論

冒泡排序雖然非常直觀且易於理解和實現,但對於解決大多數問題來說非常不切實際。

它的平均和最壞情況運行時間為 O(n 2 ) , 並且只能在 O(n) 的最佳情況下運行 當數組已經排序時。

它的空間複雜度是O(1) ,這很棒 .不幸的是,這還不足以彌補可怕的時間複雜度。

即使在簡單的 O(n 2 ) 排序算法,插入排序或選擇排序通常效率更高。

由於其簡單性,冒泡排序經常被用作計算機科學入門課程中排序算法的介紹。


Tutorial JavaScript 教程
  1. 使用 RethinkDB 和 React Native 進行實時應用開發

  2. 當條件改變時更新 .map() 中的 UI?

  3. 從回調地獄到回調天堂

  4. JavaScript Hello World |警報功能 |打印示例

  5. 如何向複製的網絡文本添加額外信息

  6. 扭曲的重新渲染 |反應性能優化

  7. 異步和等待

  1. 使用谷歌瀏覽器調試和編輯嵌入在 HTML 頁面中的 javascript

  2. 響應式排版

  3. 我在我的 Discord 機器人上添加“自動審核”功能時遇到問題

  4. Vue CLI 教程

  5. 製作 Vuetify 儀表板模板

  6. 在JS中以遞歸方式向上和向下計數

  7. 數組方法快速瀏覽

  1. 在 React-JS 中實現受保護的路由和身份驗證

  2. 什麼是 debounce 和 throttle 函數,你如何用 JavaScript 和 React 編寫它們?

  3. 了解 React Proptypes

  4. 使用 SVG 生成 blob 字符!