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

創(chuàng)新互聯(lián)是一家專業(yè)提供天臺企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、html5、小程序制作等業(yè)務(wù)。10年已為天臺眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站制作公司優(yōu)惠進(jìn)行中。

javascript欄目在本文中，我們學(xué)習(xí) Merge Sort 背后的邏輯，并用 JavaScript 實(shí)現(xiàn)。最后，在空間和時(shí)間復(fù)雜度方面將歸并排序與其他算法進(jìn)行比較。

歸并排序背后的邏輯

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

以下是歸并排序的步驟：

1. 將給定的列表分為兩半（如果列表中的元素?cái)?shù)為奇數(shù)，則使其大致相等）。

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

3. 從單個(gè)元素?cái)?shù)組開始，合并子數(shù)組，以便對每個(gè)合并的子數(shù)組進(jìn)行排序。

4. 重復(fù)第 3 步單元，直到最后得到一個(gè)排好序的數(shù)組。

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

用 JavaScript 實(shí)現(xiàn)歸并排序

首先實(shí)現(xiàn)一個(gè)將兩個(gè)已排序子數(shù)組合并為一個(gè)已排序數(shù)組的函數(shù) merge() 。要注意著兩個(gè)子數(shù)組是已經(jīng)被排好序的，這一點(diǎn)非常重要， merge() 函數(shù)只用于其進(jìn)行合并。

可以通過遍歷這兩個(gè)子數(shù)組來實(shí)現(xiàn)：

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

在這個(gè)函數(shù)中，通過把兩個(gè)排好序的子數(shù)組（left、right）合并來獲得一個(gè)排好序的大數(shù)組。首先，創(chuàng)建一個(gè)空數(shù)組。之后在 left 和 right 兩個(gè)子數(shù)組中最小元素中的較小的一個(gè)，并將其添加到空數(shù)組。我們只需要檢查 left 和 right 子數(shù)組中的第一個(gè)元素，因?yàn)樗鼈兪且雅藕眯虻摹?/p>

在這個(gè)過程中，從子數(shù)組中刪除了被選擇的元素（通過 shift()  函數(shù)實(shí)現(xiàn)）。繼續(xù)這個(gè)過程，直到其中一個(gè)子數(shù)組變?yōu)榭?。最后把非空子?shù)組的剩余元素（因?yàn)樗鼈円呀?jīng)被排序）插入主數(shù)組的最后面。

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

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))
}

在代碼中先確定中點(diǎn)，并用 splice() 函數(shù)將數(shù)組分為兩個(gè)子數(shù)組。如果元素?cái)?shù)量為奇數(shù)，則左側(cè)的元素?cái)?shù)量會少一個(gè)。不斷的劃分?jǐn)?shù)組，直到剩下單個(gè)元素的數(shù)組（array.length < 2）。然后用之前實(shí)現(xiàn)的 merge() 函數(shù)合并子數(shù)組。

代碼實(shí)現(xiàn)后用前面的用例測試一下：

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

輸出符合預(yù)期：

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

歸并排序的效率

歸并排序的最差時(shí)間復(fù)雜度為 $O(n\\log n)$，與快速排序的最佳情時(shí)間復(fù)雜度相同。歸并排序是目前最快的排序算法之一。

與快速排序不同，歸并排序不是in-place排序算法，這意味著除了輸入數(shù)組之外，它還會占用額外的空間。這是因?yàn)槲覀兪褂昧溯o助數(shù)組來存儲子數(shù)組。歸并排序的空間復(fù)雜度為  $O(n)$。

歸并排序的另一個(gè)優(yōu)點(diǎn)是非常適合多線程，因?yàn)槊總€(gè)被劃分出的一半都可以單獨(dú)排序。另一種常見的減少歸并排序運(yùn)行時(shí)間的方法是在到達(dá)相對較小的子數(shù)組時(shí)（大約 7 個(gè)元素）使用插入排序。這是因?yàn)椴迦肱判蛟谔幚硇⌒突驇缀跖藕眯虻臄?shù)組時(shí)表現(xiàn)非常好。

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

名稱欄目：JavaScript如何實(shí)現(xiàn)歸并排序
本文地址：http://jinyejixie.com/article34/ipjese.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供標(biāo)簽優(yōu)化、網(wǎng)站排名、定制網(wǎng)站、、網(wǎng)站改版、企業(yè)建站

廣告

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