使用歸併排序遞迴排序 JavaScript 陣列

在本問題陳述中，我們的目標是使用歸併排序遞迴排序陣列並藉助 Javascript 實現程式碼。因此，在下面我們將討論歸併排序及其實現。

理解問題陳述

問題陳述是編寫一個 Javascript 中歸併排序的函式，該函式將有助於將給定的輸入陣列排序為升序或降序。並且我們必須建立一個將遞迴排序元素的函式。

什麼是遞迴排序技術？

遞迴是一種函式呼叫自身來解決問題的方法。當一個函式呼叫自身時，它會在棧上建立一個新的函式例項，並且函式會繼續執行，直到找到所需的結果。此結果是停止遞歸併允許函式給出結果的條件。

因此，遞迴是一種強大的技術，它可以簡化複雜的問題，並使程式碼更簡單、更簡潔。因此，務必謹慎使用遞迴，因為如果實現不正確，它會導致堆疊溢位錯誤。

什麼是歸併排序演算法？

在歸併排序中，該演算法透過將陣列遞迴分解成更小的子陣列來排序陣列，直到每個子陣列包含一個元素。然後，該演算法將相鄰的子陣列對合併成更大且排序的子陣列。此過程遞迴執行，直到陣列的整個元素未排序。

遞迴步驟包括在陣列的左右部分上呼叫歸併排序函式。這些部分本身就是陣列。此呼叫透過將其分解成更小的子陣列來對陣列的每一半部分進行排序。一旦它分離了所有元素，演算法就開始將排序後的子數組合並回一起，以建立最終的排序陣列。

給定問題的邏輯

對於程式碼，我們將建立一個函式來執行歸併排序。並且在函式內部，我們將陣列劃分為更小的子陣列，遞迴排序這些子陣列，然後將它們合併回一起以生成一個完全排序的陣列。該函式的關鍵操作是合併步驟，其中兩個排序的子數組合併成一個排序的陣列。

演算法

步驟 1 - 宣告一個名為 mergeSort 的函式，該函式使用陣列引數。

步驟 2 - 在函式內部，我們將檢查陣列的長度是否為 1 或小於 1，它已經排序，因此只需返回陣列。

步驟 3 - 否則，我們將陣列劃分為兩個子陣列 left 和 right，並使用 mergeSort 遞迴排序每一半部分。

步驟 4 - 並且一旦遞迴呼叫返回，我們將使用 merge 函式將排序後的 left 和 right 部分合並在一起。

步驟 5 - merge 函式將獲取兩個排序的陣列 left 和 right，並將它們合併成一個排序的陣列作為結果。

演算法程式碼

//function to sort the given array
function mergeSort(arr) {
   if (arr.length <= 1) {
      return arr;
   }
   const mid = Math.floor(arr.length / 2);
   const left = arr.slice(0, mid);
   const right = arr.slice(mid);
   return merge(mergeSort(left), mergeSort(right));
}
 
//function to merge the left and right elements
function merge(left, right) {
   const result = [];
    
   while (left.length && right.length) {
      if (left[0] < right[0]) {
         result.push(left.shift());
      } else {
         result.push(right.shift());
      }
   }
    
   return [...result, ...left, ...right];
}
const arr = [4, 1, 5, 2, 6, 3, 7, 8];
console.log(mergeSort(arr));

複雜度

mergeSort 函式花費的時間為 O(n log n)，因為我們已實現歸併排序，它需要 O(n log n) 時間來對專案進行排序。而 n 是給定陣列的大小。並且程式碼使用的空間也是 O(n)，因為它將結果儲存為排序陣列。因此，此技術使其成為大型資料集的有效排序演算法。

結論

因此，上面建立的函式可用於對大小為 n 的給定陣列進行排序，時間複雜度為 O(n log n)。這是一種可靠且高效的排序演算法。

更新於： 2023年5月18日

2K+ 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告