沐鳴下載_JavaScript 實現歸併排序

在本文中,我們學習 Merge Sort 背後的邏輯,並用 JavaScript 實現。最後,在空間和時間複雜度方面將歸併排序與其他算法進行比較。

歸併排序背後的邏輯

歸併排序使用分而治之的概念對給定的元素列表進行排序。它將問題分解為較小的子問題,直到它們變得足夠簡單以至可以直接解決為止。

以下是歸併排序的步驟:

  1. 將給定的列表分為兩半(如果列表中的元素數為奇數,則使其大致相等)。
  2. 以相同的方式繼續劃分子數組,直到只剩下單個元素數組。
  3. 從單個元素數組開始,合併子數組,以便對每個合併的子數組進行排序。
  4. 重複第 3 步單元,直到最後得到一個排好序的數組。

以數組 [4, 8, 7, 2, 11, 1, 3] 為例,讓我們看一下歸併排序是如何工作的:


用 JavaScript 實現歸併排序

首先實現一個將兩個已排序子數組合併為一個已排序數組的函數 merge() 。要注意着兩個子數組是已經被排好序的,這一點非常重要, merge() 函數只用於其進行合併。

可以通過遍歷這兩個子數組來實現:

function merge(left, right) {
    let arr = []
    // 如果任何一個數組為空,就退出循環
    while (left.length && right.length) {
        // 從左右子數組的最小元素中選擇較小的元素
        if (left[0] < right[0]) {
            arr.push(left.shift())  
        } else {
            arr.push(right.shift()) 
        }
    }
    
    // 連接剩餘的元素,防止沒有把兩個數組遍歷完整
    return [ ...arr, ...left, ...right ]
}

在這個函數中,通過把兩個排好序的子數組(left、right)合併來獲得一個排好序的大數組。首先,創建一個空數組。之後在 left 和 right 兩個子數組中最小元素中的較小的一個,並將其添加到空數組。我們只需要檢查 left 和 right 子數組中的第一個元素,因為它們是已排好序的。

在這個過程中,從子數組中刪除了被選擇的元素(通過 shift() 函數實現)。繼續這個過程,直到其中一個子數組變為空。最後把非空子數組的剩餘元素(因為它們已經被排序)插入主數組的最後面。

現在有了合併兩個已排序數組的代碼,接下來為實現歸併排序算法的最終代碼。這意味着要繼續分割數組,直到最終只包含一個元素的數組為止:

function mergeSort(array) {
  const half = array.length / 2
  
  if(array.length < 2){
    return array 
  }
  
  const left = array.splice(0, half)
  return merge(mergeSort(left),mergeSort(array))
}

在代碼中先確定中點,並用 splice() 函數將數組分為兩個子數組。如果元素數量為奇數,則左側的元素數量會少一個。不斷的劃分數組,直到剩下單個元素的數組(array.length < 2)。然後用之前實現的 merge() 函數合併子數組。

代碼實現後用前面的用例測試一下:

array = [4, 8, 7, 2, 11, 1, 3];
console.log(mergeSort(array));

輸出符合預期:

1,2,3,4,7,8,11

歸併排序的效率

歸併排序的最差時間複雜度為 $O(n\\log n)$,與快速排序的最佳情時間複雜度相同。歸併排序是目前最快的排序算法之一。

與快速排序不同,歸併排序不是in-place排序算法,這意味着除了輸入數組之外,它還會佔用額外的空間。這是因為我們使用了輔助數組來存儲子數組。歸併排序的空間複雜度為 $O(n)$。

歸併排序的另一個優點是非常適合多線程,因為每個被劃分出的一半都可以單獨排序。另一種常見的減少歸併排序運行時間的方法是在到達相對較小的子數組時(大約 7 個元素)使用插入排序。這是因為插入排序在處理小型或幾乎排好序的數組時表現非常好。

總結

在本文中,我們了解了Merge Sort算法背後的邏輯,並用 JavaScript 實現。它是基本排序算法之一,可以幫助我們更好的了解分治法策略。

原文:https://stackabuse.com/merge-sort-in-javascript/

    站長推薦

    1.雲服務推薦: 國內主流雲服務商,各類雲產品的最新活動,優惠券領取。地址:阿里雲騰訊雲華為雲

    2.廣告聯盟: 整理了目前主流的廣告聯盟平台,如果你有流量,可以作為參考選擇適合你的平台點擊進入

    鏈接: http://www.fly63.com/article/detial/9812