小編給大家分享一下JavaScript如何實現歸并排序，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

創(chuàng)新互聯公司是一家專業(yè)從事網站設計、成都網站建設、網頁設計的品牌網絡公司。如今是成都地區(qū)具影響力的網站設計公司,作為專業(yè)的成都網站建設公司,創(chuàng)新互聯公司依托強大的技術實力、以及多年的網站運營經驗,為您提供專業(yè)的成都網站建設、營銷型網站建設及網站設計開發(fā)服務！

javascript欄目在本文中，我們學習 Merge Sort 背后的邏輯，并用 JavaScript 實現。最后，在空間和時間復雜度方面將歸并排序與其他算法進行比較。

歸并排序背后的邏輯

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

以下是歸并排序的步驟：

1. 將給定的列表分為兩半（如果列表中的元素數為奇數，則使其大致相等）。

2. 以相同的方式繼續(xù)劃分子數組，直到只剩下單個元素數組。

3. 從單個元素數組開始，合并子數組，以便對每個合并的子數組進行排序。

4. 重復第 3 步單元，直到最后得到一個排好序的數組。

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

用 JavaScript 實現歸并排序

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

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

function merge(left, right) {
    let arr = []
    // 如果任何一個數組為空，就退出循環(huán)
    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）合并來獲得一個排好序的大數組。首先，創(chuàng)建一個空數組。之后在left 和right 兩個子數組中最小元素中的較小的一個，并將其添加到空數組。我們只需要檢查left 和right 子數組中的第一個元素，因為它們是已排好序的。

在這個過程中，從子數組中刪除了被選擇的元素（通過shift()  函數實現）。繼續(xù)這個過程，直到其中一個子數組變?yōu)榭铡Ｗ詈蟀逊强兆訑到M的剩余元素（因為它們已經被排序）插入主數組的最后面。

現在有了合并兩個已排序數組的代碼，接下來為實現歸并排序算法的最終代碼。這意味著要繼續(xù)分割數組，直到最終只包含一個元素的數組為止：

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)$。

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

看完了這篇文章，相信你對“JavaScript如何實現歸并排序”有了一定的了解，如果想了解更多相關知識，歡迎關注創(chuàng)新互聯行業(yè)資訊頻道，感謝各位的閱讀！

網頁名稱：JavaScript如何實現歸并排序-創(chuàng)新互聯
網站路徑：http://chinadenli.net/article4/dghgie.html

成都網站建設公司_創(chuàng)新互聯，為您提供靜態(tài)網站、網頁設計公司、全網營銷推廣、網站導航、網站設計、關鍵詞優(yōu)化

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯