如何在JavaScript中實現歸併排序？

歸併排序

歸併排序演算法，我們可以按特定順序對元素進行排序。該演算法也被認為是分治策略的一個例子。在歸併排序演算法中，首先將陣列分成兩部分，然後以特定排序的方式組合。

陣列將被分成兩半，直到無法再分割。這意味著如果陣列完全分割並且無法進一步分割，則停止分割。我們將陣列分成兩半，並在每一半上實現歸併排序。該演算法是一個將兩個較小的分割陣列組合成較大的陣列的過程。

輸入輸出場景

考慮一個數組，其中包含一些未排序的隨機順序的元素，我們可以透過執行歸併排序來對這些元素進行排序。讓我們檢查下面的場景。

Input = [12, 34, 11, 1, 54, 25, 67, 45]; 
Output = 1, 11, 12, 25, 34, 45, 54, 67

正如我們在輸出中看到的，元素已經按升序排序。

歸併排序是如何工作的？

要了解歸併排序的工作方式，讓我們假設一個數組arr= [30, 20, 40, 0, 10, 80, 11]。

  • 首先，我們需要檢查陣列的左索引是否小於陣列的右索引，如果陣列滿足條件，則計算陣列的中點。


  • 現在我們需要將包含 7 個元素的陣列分成兩個大小分別為 4 和 3 的陣列。

  • 將陣列分成兩半後，它將如下所示。


  • 將陣列繼續分成兩半，直到陣列不能再分割。


  • 將所有元素分成最小單元后，現在根據元素的大小比較元素。

  • 首先比較每個列表中陣列的元素，然後對其進行排序並將其合併到另一個列表中。


  • 執行所有合併後，將得到以下列表。


演算法

讓我們看看演算法：

  • 宣告一個數組、左索引、右索引和中間變數。

  • 執行歸併排序。

    mergesort(array, left index, right index)

    如果左索引 > 右索引

    返回

    mid= (左索引 + 右索引) / 2

    mergesort(array, 左索引, mid) // 上半部分

    mergesort(array, mid+1, 右索引) // 下半部分

    merge(array, 左索引, mid, 右索引) // 合併上述步驟中排序的兩半

示例

在下面的示例中，為了執行歸併排序，我們建立了一個包含隨機順序元素的陣列。並使用歸併排序演算法將陣列元素按升序排序。

<!DOCTYPE html> 
<html> 
   <title>Merge Sort</title> 
<head> 
   <script> 
      function merge_Arrays(left_sub_array, right_sub_array) {
         let array = []
         while (left_sub_array.length && right_sub_array.length) {
            if (left_sub_array[0] < right_sub_array[0]) {
               array.push(left_sub_array.shift())
            } else {
               array.push(right_sub_array.shift())
            }
         }
         return [ ...array, ...left_sub_array, ...right_sub_array ]
      }
      function merge_sort(unsorted_Array) {
         const middle_index = unsorted_Array.length / 2
         if(unsorted_Array.length < 2) {
            return unsorted_Array
         }
         const left_sub_array = unsorted_Array.splice(0, middle_index)
         return merge_Arrays(merge_sort(left_sub_array),merge_sort(unsorted_Array))
      }
      unsorted_Array = [39, 28, 44, 4, 10, 83, 11];
      document.write("The sorted array will be: ",merge_sort(unsorted_Array));
   </script> 
</head>  
<body> 
</body> 
</html>

注意

  • 與其他排序演算法相比，歸併排序演算法的執行速度較慢。

  • 即使陣列已排序，它也會遍歷整個排序過程。

  • 此演算法還需要 0(n) 的額外記憶體空間用於臨時陣列。

更新於： 2022年9月23日

9K+ 瀏覽量

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告
© . All rights reserved.